Publications related to Approximation-preserving reduction

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

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

Complexity Constrained Representation Selection for Dynamic Adaptive Streaming

Pascal Frossard, Laura Toni, Chenglin Li

In this paper, we propose a representation selection optimization problem for complexity constrained adaptive video streaming that properly takes into account the different complexity-rate-distortion (C-R-D) characteristics of the videos when implementing ...

Ieee2016

APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION

Ola Nils Anders Svensson

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + root 3 + epsilon, improving upon the decade-old ratio of 3 + epsilon. Our improved approximation ratio is achieved by exploiting the power of pseudo-app ...

Siam Publications2016

An Exact Algorithm to Compute the Double-Cut-and-Join Distance for Genomes with Duplicate Genes

Bernard Moret, Yu Lin, Mingfu Shao

Computing the edit distance between two genomes is a basic problem in the study of genome evolution. The double-cut-and-join (DCJ) model has formed the basis for most algorithmic research on rearrangements over the last few years. The edit distance under t ...

Mary Ann Liebert2015

Strong LP formulations for scheduling splittable jobs on unrelated machines

Ola Nils Anders Svensson

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this ...

Springer Heidelberg2015

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.

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

Approximation-preserving reduction

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Maximizing Symmetric Submodular Functions

A New Framework for Distributed Submodular Maximization

Complexity Constrained Representation Selection for Dynamic Adaptive Streaming

APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION

Maximizing k-Submodular Functions and Beyond

An Exact Algorithm to Compute the Double-Cut-and-Join Distance for Genomes with Duplicate Genes

Strong LP formulations for scheduling splittable jobs on unrelated machines

Graph Chatbot

Chat with Graph Search

Strong LP formulations for scheduling splittable jobs on unrelated machines

Maximizing Symmetric Submodular Functions

Complexity Constrained Representation Selection for Dynamic Adaptive Streaming

APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION

A New Framework for Distributed Submodular Maximization

An Exact Algorithm to Compute the Double-Cut-and-Join Distance for Genomes with Duplicate Genes

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Maximizing k-Submodular Functions and Beyond