Approximation Algorithms for Allocation and Network Design
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.
We consider the following problem: Given a rational matrix A∈Qm×n and a rational polyhedron Q⊆Rm+p, decide if for all vectors b∈Rm, for which there exists an integral z∈Zp suc ...
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 ...
A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets ...
Aggregate scheduling is one of the most promising solutions to the issue of scalability in networks, like DiffServ networks and high speed switches, where hard QoS guarantees are required. For networks of FIFO aggregate schedulers, the main existing suffic ...
The idea to use error-correcting codes in order to construct public key cryptosystems was published in 1978 by McEliece [ME1978]. In his original construction, McEliece used Goppa codes, but various later publications suggested the use of different familie ...
Starting from the basic image reconstruction problem in discrete tomography some graph theoretical models are proposed. This suggests the study of some variations and extensions of the basic problem. Applications in scheduling and timetabling are described ...
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 ...
Uncertain information is commonplace in real-world data management scenarios. The ability to represent large sets of possible instances (worlds) while supporting efficient storage and processing is an important challenge in this context. The recent formali ...
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 ...
Register allocation, in high-level synthesis and ASIP design, is the process of determining the number of registers to include in the resulting circuit or processor. The goal is to allocate the minimum number of registers such that no scalar variable is sp ...
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2007
