Further Collapses in TFNP

Related publications (27)

About
Privacy
Disclaimer

Graph Chatbot

Model and metaheuristics for a scheduling problem integrating procurement, sale and distribution decisions

This paper presents an integrated approach for short-term supply chain management (SCM) at a fast moving consumer goods production plant. The problem is to determine the production quantities, to provide a detailed production schedule, to trigger the relev ...

Springer2017

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

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

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

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] ...

Assoc Computing Machinery2016

A Bi-Criteria Approximation Algorithm for k-Means

Justin Dean Ward

We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set ...

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2016

Collision-Free Pattern Formation

Rachid Guerraoui, Alexandre David Olivier Maurer

Shoals of small fishes can change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. In this paper, we study the analog problem of distributed pattern formation. A set of processes needs to move ...

2016

Parallelizing the Chambolle Algorithm for Performance Optimized Mapping on FPGA devices

David Atienza Alonso, Abdulkadir Akin, Ivan Beretta, Alessandro Antonio Nacci

The performance and the efficiency of recent computing platforms have been deeply influenced by the widespread adoption of hardware accelerators, such as Graphics Processing Units (GPUs) or Field Programmable Gate Arrays (FPGAs), which are often employed t ...

Assoc Computing Machinery2016

Page 3 of 3