A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization
Related publications (32)
Graph Chatbot
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.
Approximation algorithms are a commonly used tool for designing efficient algorithmic solutions for intractable problems, at the expense of the quality of the output solution. A prominent technique for designing such algorithms is the use of Linear Program ...
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algo ...
We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time b ...
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tig ...
We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream wi ...
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 ...
We study the stability of coherent structures in plane Couette flow against long-wavelength perturbations in wide domains that cover several pairs of coherent structures. For one and two pairs of vortices, the states retain the stability properties of the ...
Hexagonal lattice systems (e.g., triangular, honeycomb, kagome) possess a multidimensional irreducible representation corresponding to d(x2-y2) and d(xy) symmetry. Consequently, various unconventional phases that combine these d-wave representations can oc ...
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
Linear programming 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 methodo ...