Publications related to New Graph Algorithms via Polyhedral Techniques

Competitive ratio of List Scheduling on uniform machines and randomized heuristics

We study online scheduling on m uniform machines, where m - 1 of them have a reference speed 1 and the last one a speed s with 0

Springer US2011

Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective

Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic

One major concern in pervasive wireless applications is location privacy, where malicious eavesdroppers, based on static device identifiers, can continuously track users. As a commonly adopted countermeasure to prevent such identifier-based tracking, devic ...

Springer2011

Bin Packing via Discrepancy of Permutations

Friedrich Eisenbrand, Thomas Rothvoss, Doemoetoer Palvoelgyi

A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxati ...

Siam, 3600 Univ City Science Center, Philadelphia, Pa 19104-2688 Usa2011

On the Approximability of Single-Machine Scheduling with Precedence Constraints

Ola Nils Anders Svensson

We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cove ...

2011

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Dominique de Werra, Bernard Ries

Given an undirected graph G = (V, E) with matching number nu(G), a d-blocker is a subset of edges B such that nu((V, E \ B))

2010

Optimal selection of customers for a last-minute offer

Thomas Rothvoss

We analyze a short-term revenue optimization problem that involves the optimal targeting of customers for a promotion in which a finite number of perishable items are sold on a last-minute offer. The goal is to select the subset of customers to whom the of ...

Informs2010

The interval constrained 3-coloring problem

Laura Sanità

In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-co ...

Springer Verlag2010

Testing additive integrality gaps

Friedrich Eisenbrand, Nicolai Hähnle, Gennady Shmonin

We consider the problem of testing whether the maximum integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomi ...

2010

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

Martin Vetterli, Patrick Thiran, Florence Bénézit

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any conn ...

IEEE2010

New Graph Algorithms via Polyhedral Techniques

Graph Chatbot

Chat with Graph Search

Competitive ratio of List Scheduling on uniform machines and randomized heuristics

Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective

Bin Packing via Discrepancy of Permutations

On the Approximability of Single-Machine Scheduling with Precedence Constraints

An Improved LP-based Approximation for Steiner Tree

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Optimal selection of customers for a last-minute offer

The interval constrained 3-coloring problem

Testing additive integrality gaps

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

Bin Packing via Discrepancy of Permutations

Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective

On the Approximability of Single-Machine Scheduling with Precedence Constraints

An Improved LP-based Approximation for Steiner Tree

Optimal selection of customers for a last-minute offer

The interval constrained 3-coloring problem

Testing additive integrality gaps

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

Competitive ratio of List Scheduling on uniform machines and randomized heuristics

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid