Publications associées à Approximation-preserving reduction

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho aro ...

SPRINGER HEIDELBERG2021

Fair Colorful k-Center Clustering

Ola Nils Anders Svensson, Xinrui Jia

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around ...

Springer2020

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Ola Nils Anders Svensson, Ashkan Norouzi Fard, Justin Dean Ward

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for k-means in Euclidean space with a provable guarantee is a simple local ...

SIAM PUBLICATIONS2020

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature

Maryam Kamgarpour, Andreas Krause

Games with continuous strategy sets arise in several machine learning problems (e.g. adversarial learning). For such games, simple no-regret learning algorithms exist in several cases and ensure convergence to coarse correlated equilibria (CCE). The effic ...

PMLR2019

Robust Maximization of Non-Submodular Objectives

Volkan Cevher, Ilija Bogunovic, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exi ...

2018

Deterministic Algorithms for Submodular Maximization Problems

Moran Feldman

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all c ...

ASSOC COMPUTING MACHINERY2018

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of th ...

ASSOC COMPUTING MACHINERY2018

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.

Approximation-preserving reduction

Fair colorful k-center clustering

Fair Colorful k-Center Clustering

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Model-based predictive control methods for distributed energy resources in smart grids.

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature

Robust Maximization of Non-Submodular Objectives

Deterministic Algorithms for Submodular Maximization Problems

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Algorithms For Clustering Problems

Graph Chatbot

Chattez avec Graph Search

Fair colorful k-center clustering

Fair Colorful k-Center Clustering

Model-based predictive control methods for distributed energy resources in smart grids.

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Robust Maximization of Non-Submodular Objectives

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Algorithms For Clustering Problems

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature

Deterministic Algorithms for Submodular Maximization Problems