Publication

Santa Claus Schedules Jobs On Unrelated Machines

Related publications (191)

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.

Preemptive open shop scheduling with multiprocessors: polynomial cases and applications

Dominique de Werra

This paper addresses a multiprocessor generalization of the preemptive open-shop scheduling problem. The set of processors is partitioned into two groups and the operations of the jobs may require either single processors in either group or simultaneously ...

2004

Applying interchangeability techniques to the distributed breakout algorithm

Boi Faltings, Adrian Petcu

In this paper, we develop two methods for improving the performance of the standard Distributed Breakout Algorithm \cite{yokoo:dba} using the notion of interchangeability. We study the performance of this algorithm on the problem of distributed sensor netw ...

2004

Networked Slepian-Wolf: Theory and Algorithms

Martin Vetterli, Razvan Cristescu

In this paper, we consider the minimization of a relevant energy consumption related cost function in the context of sensor networks where correlated sources are generated at various sets of source nodes and have to be transmitted to some set of sink nodes ...

Springer Verlag2004

Networked Slepian-Wolf: Theory and Algorithms

Martin Vetterli, Razvan Cristescu

2004

Genomic distances under deletions and insertions

Bernard Moret, Krister Swenson

As more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, deletions, and movements of genes along its chromo ...

2004

Using the Breakout Algorithm to Identify Hard and Unsolvable Subproblems

Boi Faltings, Carlos Eisenberg

Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for highly constrained or overconstrained ...

Swiss Federal Institute of Technology (EPFL)2003

A polynomial case of inconstrained zero-one queadratic optimization

Thomas Liebling, Kim Alexandre Allemand

Unconstrained zero-one quadratic maximization problems can be solved in polynomial time when the symmetric matrix describing the objective function is positive semidefinite of fixed rank with known spectral decomposition. ...

2001

Maintaining minimum spanning forests in dynamic graphs

Monika Henzinger

We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time o(sqrt(n)) per operation. To be precise, the algorithm uses O(n1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. ...

2001

Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

We consider the cocircuit graph GM of an oriented matroid M, which is the 1-skeleton of the cell complex formed by the span of the cocircuits of M. As a result of Cordovil, Fukuda, and Guedes de Oliveira, the isomorphism class of M is not determined by GM, ...

2001

An efficient Fault Localization Algorithm for IP/WDM Networks

Patrick Thiran, Carmen Mas

We propose an algorithm for localizing multiple failures in an IP/WDM network. They can be either hard failures (unexpected events that interrupt suddenly the established channels) or soft failures (events that progressively degrade the quality of transmis ...

2000