Publications related to New Results in the Theory of Linear and Integer Programming

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

The number of distinct distances from a vertex of a convex polygon

János Pach, Rom Pinchasi, Gabriel Nivasch

Erd\H{o}s conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least floor(n/2) distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 - O(1). I ...

2013

Reconstructing Loopy Curvilinear Structures Using Integer Programming

Pascal Fua, Engin Türetken, Fethallah Benmansour

We propose a novel approach to automated delineation of linear structures that form complex and potentially loopy networks. This is in contrast to earlier approaches that usually assume a tree topology for the networks. At the heart of our method is an Int ...

Ieee2013

An exact algorithm for the integrated planning of berth allocation and quay crane assignment

Michel Bierlaire, Matteo Salani, Ilaria Vacca

In this paper we study the simultaneous optimization of berth allocation and quay crane assignment in seaport container terminals. We propose a model based on an exponential number of variables that is solved via column generation. An exact branch and pric ...

Informs2013

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

Data Exchange Problem with Helpers

Michael Christoph Gastpar, Sameer Pawar

In this paper we construct a deterministic polyno- mial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another ...

2012

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [1] pro ...

Springer2012

New Results in the Theory of Linear and Integer Programming

Graph Chatbot

Chat with Graph Search

The School Bus Problem on Trees

The number of distinct distances from a vertex of a convex polygon

Reconstructing Loopy Curvilinear Structures Using Integer Programming

An exact algorithm for the integrated planning of berth allocation and quay crane assignment

Approximating k-median via pseudo-approximation

Understanding and improving relational matrix factorization in recommender systems

Santa Claus Schedules Jobs On Unrelated Machines

Polynomial Approximations for Continuous Linear Programs

Data Exchange Problem with Helpers

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation

Data Exchange Problem with Helpers

The School Bus Problem on Trees

Polynomial Approximations for Continuous Linear Programs

The number of distinct distances from a vertex of a convex polygon

Understanding and improving relational matrix factorization in recommender systems

Approximating k-median via pseudo-approximation

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation

An exact algorithm for the integrated planning of berth allocation and quay crane assignment

Reconstructing Loopy Curvilinear Structures Using Integer Programming

Santa Claus Schedules Jobs On Unrelated Machines