Publication

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Related publications (43)

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.

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

Friedrich Eisenbrand, Thomas Rothvoss

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 ...

Springer2008

Towards a Theory of Robust Localization against Malicious Beacon Nodes

Murtuza Jadliwala

Localization in the presence of malicious beacon nodes is an important problem in wireless networks. Although significant progress has been made on this problem, some fundamental theoretical questions still remain unanswered: in the presence of malicious b ...

IEEE Computer Society2008

New Results on Optimizing Rooted Triplets Consistency

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 ...

Springer2008

An approach to modelling and verification of component based systems

Joseph Sifakis

We build on a framework for modelling and investigating component-based systems that strictly separates the description of behavior of components from the way they interact. We discuss various properties of system behavior as liveness, local progress, loca ...

2007

TCHo: a Hardware-Oriented Trapdoor Cipher

Serge Vaudenay, Willi Meier, Jean-Philippe Aumasson

This paper improves the Finiasz-Vaudenay construction of TCHo, a hardware-oriented public-key cryptosystem, whose security relies in the hardness of finding a low-weight multiple of a given polynomial, and on the decoding of certain noisy cyclic linear cod ...

Springer2007

New polynomial-time algorithms for Camion bases

Antoine Musitelli

Let M be a finite set of vectors in Rn of cardinality m and H(M) = {{x ∈ Rn : cTx = 0} : c ∈ M} the central hyperplane arrangement represented by M. An independent subset of M of cardinality n is called a Camion basis, if it determines a simplex region in ...

2006

Computing All Faces of the Minkowski Sum of V-Polytopes

Christophe Weibel

We consider the problem of listing faces of the Minkowski sum of several V-polytopes in R^d. An algorithm for listing all faces of dimension up to j is presented, for any given 0

2005

Active measurement for multiple link failure diganosis in IP networks

Patrick Thiran, Xuan Hung Nguyen

Simultaneous link failures are common in IP networks \cite{Markopoulou04}. In this paper, we develop a technique for locating multiple failures in Service Provider or Enterprise IP networks using active measurement. We propose a two-phased approach that mi ...

2004

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

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