Publication

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Related publications (36)

Graph Chatbot

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.

Applications of Strong Convex Relaxations to Allocation Problems

Christos Kalaitzis

Approximation algorithms are a commonly used tool for designing efficient algorithmic solutions for intractable problems, at the expense of the quality of the output solution. A prominent technique for designing such algorithms is the use of Linear Program ...

EPFL2017

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

A New Framework for Distributed Submodular Maximization

Justin Dean Ward

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algo ...

Ieee2016

On the configuration LP for maximum budgeted allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Lukas Polacek, Aleksander Madry

We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integral ...

Springer Heidelberg2015

Strong LP formulations for scheduling splittable jobs on unrelated machines

Ola Nils Anders Svensson

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this ...

Springer Heidelberg2015

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

On the Configuration LP for Maximum Budgeted Allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Lukas Polacek, Aleksander Madry

We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integral ...

Springer2014

Centrality of Trees for Capacitated k-Center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated k-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) k locations (called centers) and assign e ...

Springer2014

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Steiner Tree Approximation via Iterative Randomized Rounding

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental 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 this problem w ...

Assoc Computing Machinery2013

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

3

. Then, we draw a connection to Goem ...

EPFL2014