Publication

Algorithms For Clustering Problems

Related publications (107)

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.

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

Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm

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

Approximating Parameterized Convex Optimization Problems.

Martin Jaggi

We extend Clarkson's framework by considering parameterized convex optimization problems over the unit simplex, that depend on one parameter. We provide a simple and efficient scheme for maintaining an ε-approximate solution (and a corresponding ε-coreset) ...

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

Springer2009

Parametric integer programming in fixed dimension

Friedrich Eisenbrand, Gennady Shmonin

We consider the following problem: Given a rational matrix

A \in \mathbb{Q}^{m \times n}

and a rational polyhedron

Q \subseteq \mathbb{R}^{m+p}

, decide if for all vectors

b \in \mathbb{R}^m

, for which there exists an integral

z \in \mathbb{Z}^p

suc ...

2008

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

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

Springer2007

New Algorithms for Approximate Nash Equilibria in Bimatrix Games

We consider the problem of computing additively approximate Nash equilibria in non-cooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. Our work improves the previously best known (0. ...

Springer2007

Average case analysis of multichannel sparse approximations using p- thresholding

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces

p

-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latte ...

2007

Average case analysis of multichannel sparse approximations using p-thresholding - art. no. 67011X

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latter ...

Spie-Int Soc Optical Engineering, Po Box 10, Bellingham, Wa 98227-0010 Usa2007