Problème de l'arbre de Steiner

Science formelle
Mathématiques
Mathématiques discrètes
Théorie des graphes

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (27)

An Efficient Streaming Algorithm for the Submodular Cover Problem

Volkan Cevher, Ilija Bogunovic, Ya-Ping Hsieh, Ashkan Norouzi Fard, Abbas Bazzi, Marwa El Halabi

We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream wi ...

2016

Network design of a transport system based on accelerating moving walkways

Michel Bierlaire, Riccardo Scarinci, Iliya Dimitrov Markov

Pollution, congestion and urbanistic considerations are leading to a change in the use of private vehicles in dense city centers. More frequently, the last-mile is covered with systems such as public transport, car sharing and bike sharing as well as an in ...

2016

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

Charles Babbage Res Ctr2016

Removing and Adding Edges for the Traveling Salesman Problem

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a d ...

Assoc Computing Machinery2016

Enforcing Efficient Equilibria in Network Design Games via Subsidies

Christos Kalaitzis

The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting net ...

Springer Verlag2015

Sparse Group Covers and Greedy Tree Approximations

Volkan Cevher, Luca Baldassarre

We consider the problem of finding a K-sparse approximation of a signal, such that the support of the approximation is the union of sets from a given collection, a.k.a. group structure. This problem subsumes the one of finding K-sparse tree approximations. ...

2015

Centrality of trees for capacitated -center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each ...

Springer Heidelberg2015

Page 2 sur 2