Publications related to Approximation-preserving reduction

Deterministic Algorithms for Submodular Maximization Problems

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

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

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Volkan Cevher, Ilija Bogunovic, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakub Tarnawski

We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fashion and (ii) m items from the algorithm’s memory might be removed after th ...

2017

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

Abstract—In this paper, we consider the problem of maximizing a monotone submodular function subject to a cardinality constraint, with two added twists: The computation is distributed across a number of machines, and we require the solution to be robust ag ...

2017

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

Symplectic Dynamical Low Rank approximation of wave equations with random parameters

Fabio Nobile, Eleonora Musharbash

In this paper we propose a dynamical low-rank strategy for the approximation of second order wave equations with random parameters. The governing equation is rewritten in Hamiltonian form and the approximate solution is expanded over a set of

2S

dynamica ...

2017

MATHICSE Technical Report : Symplectic dynamical low rank approximation of wave equations with random parameters

Fabio Nobile, Eleonora Musharbash, Eva Vidlicková

In this paper we propose a dynamical low-rank strategy for the approximation of second order wave equations with random parameters. The governing equation is rewritten in Hamiltonian form and the approximate solution is expanded over a set of 2S dynamical ...

MATHICSE2017

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

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

Approximation-preserving reduction

Graph Chatbot

Chat with Graph Search

Deterministic Algorithms for Submodular Maximization Problems

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

Algorithms For Clustering Problems

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Symplectic Dynamical Low Rank approximation of wave equations with random parameters

MATHICSE Technical Report : Symplectic dynamical low rank approximation of wave equations with random parameters

Strengths and Limitations of Linear Programming Relaxations

Maximizing Symmetric Submodular Functions

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Maximizing Symmetric Submodular Functions

MATHICSE Technical Report : Symplectic dynamical low rank approximation of wave equations with random parameters

Strengths and Limitations of Linear Programming Relaxations

Deterministic Algorithms for Submodular Maximization Problems

Algorithms For Clustering Problems

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

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Symplectic Dynamical Low Rank approximation of wave equations with random parameters