Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability
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.
Abstract We give a new randomized LP-rounding 1.725-approximation algorithm for the metric Fault- Tolerant Uncapacitated Facility Location problem. This improves on the previously best known 2.076-approximation algorithmof Swamy & Shmoys. To the best of ou ...
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010
We present a polynomial time approximation scheme for the real-time scheduling problem with fixed priorities when resource augmentation is allowed. For a fixed ε > 0, our algorithmcomputes an assignment using atmost (1+ε)·OPT +1 processors in polynomial ti ...
We consider the metric uncapacitated facility location problem(UFL). In this paper we modify the (1 + 2/e)-approximation algorithm of Chudak and Shmoys to obtain a new (1.6774,1.3738)- approximation algorithm for the UFL problem. Our linear programing roun ...
In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer ...
We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks τi=(ci,pi) on a minimum number of identical machines a ...
We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...
