Publications related to New Graph Algorithms via Polyhedral Techniques

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

The School Bus Problem on Trees

Laura Sanità, Adrian Aloysius Bock

The School Bus Problem is an NP-hard vehicle routing problem in which the goal is to route buses that transport children to a school such that for each child, the distance travelled on the bus does not exceed the shortest distance from the child's home to ...

Springer US2013

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 ...

Association for Computing Machinery2013

MPTCP Is Not Pareto-Optimal: Performance Issues and a Possible Solution

Jean-Yves Le Boudec, Nicolas Gabriel Gast, Ramin Khalili, Miroslav Popovic

Multipath TCP (MPTCP) has been proposed recently as a mechanism for transparently supporting multiple connections to the application layer. It is under discussion at the IETF. We nevertheless demonstrate that the current MPTCP suffers from two problems: P1 ...

Ieee-Inst Electrical Electronics Engineers Inc2013

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic

Location privacy is a major concern in pervasive networks where static device identifiers enable malicious eavesdroppers to continuously track users and their movements. In order to prevent such identifier-based tracking, devices could coordinate regular i ...

2013

New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs

Bartosz Maria Walczak

A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-pla ...

Springer International Publishing2013

Supercriticality of an annealed approximation of Boolean networks

Thomas Mountford, Daniel Rodrigues Valesin

We consider a model recently proposed by Chatterjee and Durrett [1] as an "annealed approximation" of boolean networks, which are a class of cellular automata on a random graph, as defined by S. Kauffman [5]. The starting point is a random directed graph o ...

Univ Washington, Dept Mathematics2013

Approximating k-median via pseudo-approximation

Ola Nils Anders Svensson

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + √3 + ε, improving upon the decade-old ratio of 3+ε. Our approach is based on two components, each of which, we believe, is of independent interest. Firs ...

ACM Press2013

Santa Claus Schedules Jobs On Unrelated Machines

Ola Nils Anders Svensson

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More t ...

Siam Publications2012

New Graph Algorithms via Polyhedral Techniques

Graph Chatbot

Chat with Graph Search

The School Bus Problem on Trees

Bin Packing via Discrepancy of Permutations

MPTCP Is Not Pareto-Optimal: Performance Issues and a Possible Solution

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs

The flip-graph of the 4-dimensional cube is connected

Supercriticality of an annealed approximation of Boolean networks

Approximating k-median via pseudo-approximation

New Results in the Theory of Linear and Integer Programming

Santa Claus Schedules Jobs On Unrelated Machines

New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs

The School Bus Problem on Trees

MPTCP Is Not Pareto-Optimal: Performance Issues and a Possible Solution

Bin Packing via Discrepancy of Permutations

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

The flip-graph of the 4-dimensional cube is connected

Supercriticality of an annealed approximation of Boolean networks

Approximating k-median via pseudo-approximation

New Results in the Theory of Linear and Integer Programming

Santa Claus Schedules Jobs On Unrelated Machines