Publication

Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation

Related publications (61)

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.

MATHICSE Technical Report : Low-rank approximation in the Frobenius norm by column and row subset selection

Daniel Kressner, Alice Cortinovis

A CUR approximation of a matrix A is a particular type of low-rank approximation where C and R consist of columns and rows of A, respectively. One way to obtain such an approximation is to apply column subset selection to A and its transpose. In this work, ...

MATHICSE2019

Algorithms For Clustering Problems

Ashkan Norouzi Fard

Clustering is a classic topic in combinatorial optimization and plays a central role in many areas, including data science and machine learning. In this thesis, we first focus on the dynamic facility location problem (i.e., the facility location problem in ...

EPFL2018

When Stuck, Flip a Coin

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Chidambaram Annamalai

We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain ...

Association for Computing Machinery2017

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Applications of Strong Convex Relaxations to Allocation Problems

Christos Kalaitzis

Approximation algorithms are a commonly used tool for designing efficient algorithmic solutions for intractable problems, at the expense of the quality of the output solution. A prominent technique for designing such algorithms is the use of Linear Program ...

EPFL2017

Dynamic Facility Location via Exponential Clocks

Ola Nils Anders Svensson, Ashkan Norouzi Fard, Hyung Chan An

The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance ...

Association for Computing Machinery2017

LP-Based Algorithms For Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic me ...

Society for Industrial and Applied Mathematics2017

Maximizing Symmetric Submodular Functions

Moran Feldman

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by c ...

Association for Computing Machinery2017

A single-phase, proximal path-following framework

Volkan Cevher, Quoc Tran Dinh, Anastasios Kyrillidis

We propose a new proximal, path-following framework for a class of---possibly non-smooth---constrained convex problems. We consider settings where the non-smooth part is endowed with a proximity operator, and the constraint set is equipped with a self-conc ...

INFORMS2017