Publications related to Randomized rounding

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.

LP-Based Algorithms for Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodo ...

IEEE2014

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

Scale-invariant representation of light field images for object recognition and tracking

Martin Vetterli, Alireza Ghasemi

Achieving perfect scale-invariance is usually not possible using classical color image features. This is mostly because of the fact that a traditional image is a two-dimensional projection of the real world. In contrast, light field imaging makes available ...

International Society for Optics and Photonics2014

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

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

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

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Ola Nils Anders Svensson, Klaus Jansen

We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objecti ...

Assoc Computing Machinery2012

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

The Complexity of Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2011

Randomized rounding

Graph Chatbot

Chat with Graph Search

LP-Based Algorithms for Capacitated Facility Location

Centrality of Trees for Capacitated k-Center

Scale-invariant representation of light field images for object recognition and tracking

Steiner Tree Approximation via Iterative Randomized Rounding

Bin Packing via Discrepancy of Permutations

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

Randomized versus Deterministic Implementations of Concurrent Data Structures

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Bin Packing via Discrepancy of Permutations

The Complexity of Renaming

Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability

Steiner Tree Approximation via Iterative Randomized Rounding

Bin Packing via Discrepancy of Permutations

The Complexity of Renaming

LP-Based Algorithms for Capacitated Facility Location

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

Centrality of Trees for Capacitated k-Center

Randomized versus Deterministic Implementations of Concurrent Data Structures

Bin Packing via Discrepancy of Permutations

Scale-invariant representation of light field images for object recognition and tracking