Publications related to Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Approximation algorithms for geometric dispersion

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

Submodular Stochastic Probing on Matroids

Justin Dean Ward, Marek Adamczyk

In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Mo ...

INFORMS2016

Centrality of trees for capacitated -center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) locations (called centers) and assign each ...

Springer Heidelberg2015

Anchor View Allocation for Collaborative Free Viewpoint Video Streaming

Pascal Frossard

In free viewpoint video, a viewer can choose at will any camera angle or the so-called "virtual view" to observe a dynamic 3-D scene, enhancing his/her depth perception. The virtual view is synthesized using texture and depth videos of two anchor camera vi ...

2015

On the configuration LP for maximum budgeted allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Lukas Polacek, Aleksander Madry

We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integral ...

Springer Heidelberg2015

A Tale of Two Quasi-Polynomial Algorithms

Robert Granger

In 2013 the Discrete Logarithm Problem in finite fields of small characteristic enjoyed a rapid series of developments, starting with the heuristic polynomial-time relation generation method due to Gologlu, Granger, McGuire and Zumbragel, and culminating w ...

2015

Local discontinuous Galerkin methods for fractional ordinary differential equations

Jan Sickmann Hesthaven

This paper discusses the upwinded local discontinuous Galerkin methods for the one-term/multi-term fractional ordinary differential equations (FODEs). The natural upwind choice of the numerical fluxes for the initial value problem for FODEs ensures stabili ...

2015

Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme

Boi Faltings, Immanuel Trummer

The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A s ...

Institute of Electrical and Electronics Engineers2014

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

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 so as 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 ce ...

2014

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

Graph Chatbot

Chat with Graph Search

Approximation algorithms for geometric dispersion

Submodular Stochastic Probing on Matroids

Centrality of trees for capacitated -center

Anchor View Allocation for Collaborative Free Viewpoint Video Streaming

On the configuration LP for maximum budgeted allocation

A Tale of Two Quasi-Polynomial Algorithms

Local discontinuous Galerkin methods for fractional ordinary differential equations

Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme

Node-weighted network design and maximum sub-determinants

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Node-weighted network design and maximum sub-determinants

Anchor View Allocation for Collaborative Free Viewpoint Video Streaming

Centrality of trees for capacitated -center

A Tale of Two Quasi-Polynomial Algorithms

Approximation algorithms for geometric dispersion

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Submodular Stochastic Probing on Matroids

Local discontinuous Galerkin methods for fractional ordinary differential equations

On the configuration LP for maximum budgeted allocation

Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme