Publication

Centrality of Trees for Capacitated k-Center

Publications associées (119)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Covering Cubes and the Closest Vector Problem

Friedrich Eisenbrand, Martin Niemeier, Nicolai Hähnle

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^(O(n))(log(1/epsilon ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2011

Approximability of Sparse Integer Programs

David Pritchard

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx:Ax≥b,0≤x≤d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A,b,c,d a ...

Springer-Verlag2011

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

Optimal selection of customers for a last-minute offer

Thomas Rothvoss

We analyze a short-term revenue optimization problem that involves the optimal targeting of customers for a promotion in which a finite number of perishable items are sold on a last-minute offer. The goal is to select the subset of customers to whom the of ...

Informs2010

New Algorithms for Approximate Nash Equilibria in Bimatrix Games

We consider the problem of computing additively approximate Nash equilibria in noncooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. We first provide a simpler algorithm, that achie ...

2010

Nonholonomic source seeking in switching random fields

Mahmut Selman Sakar

We consider the problem of designing controllers for nonholonomic mobile robots converging to the source (minimum) of a field. In addition to the mobility constraints posed by the nonholonomic dynamics, we assume that the field is completely unknown to the ...

2010

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...

2010

A Fault-Tolerant Token based Atomic Broadcast Algorithm

André Schiper, Nils Richard Ekwall

Many atomic broadcast algorithms have been published in the last twenty years. Token based algorithms represent a large class of these algorithms. Interestingly, all the token based atomic broadcast algorithms rely on a group membership service and none of ...

2010

An Integrative Approach to Light- and Heavy-Weighted Route Planning Problems

The single-source shortest path problem (SSSP) frequently arises in practical applications of todays Intelligent Transport Systems (ITS). E.g. for route planning or traffic assignment, several variants of Dijkstra’s algorithm or the A* algorithm have been ...

2010

A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

Thomas Rothvoss

We present a new approximation algorithm for rate-monotonic multiprocessor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k it yields solutions with at most (3/2 + 1/k)*OPT+9k many processors, thus it gives a ...

Springer2010