Publications related to Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

A Framework for the Secretary Problem on the Intersection of Matroids

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen

The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one- ...

ASSOC COMPUTING MACHINERY2018

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

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Justin Dean Ward

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or ...

INFORMS2017

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

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Nisheeth Vishnoi, Javad Ebrahimi Boroojeni, Damian Mateusz Straszak

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the sim ...

Ieee2017

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

Maximizing k-Submodular Functions and Beyond

Justin Dean Ward

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k >= 2 and 1

Assoc Computing Machinery2016

A New Framework for Distributed Submodular Maximization

Justin Dean Ward

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 ...

Ieee2016

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

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 ...

EPFL2016

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

Graph Chatbot

Chat with Graph Search

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

A Framework for the Secretary Problem on the Intersection of Matroids

Deterministic Algorithms for Submodular Maximization Problems

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Maximizing Symmetric Submodular Functions

Maximizing k-Submodular Functions and Beyond

A New Framework for Distributed Submodular Maximization

Approximation algorithms for geometric dispersion

Deterministic Algorithms for Submodular Maximization Problems

Maximizing Symmetric Submodular Functions

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

A Framework for the Secretary Problem on the Intersection of Matroids

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Maximizing k-Submodular Functions and Beyond

A New Framework for Distributed Submodular Maximization

Approximation algorithms for geometric dispersion