Publications related to Robust Maximization of Non-Submodular Objectives

Robustness via curvature regularization, and vice versa

Pascal Frossard, Seyed Mohsen Moosavi Dezfooli, Alhussein Fawzi

State-of-the-art classifiers have been shown to be largely vulnerable to adversarial perturbations. One of the most effective strategies to improve robustness is adversarial training. In this paper, we investigate the effect of adversarial training on the ...

2018

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

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

Gaussian Curvature as an Identifier of Shell Rigidity

Davit Harutyunyan

In the paper we deal with shells with non-zero Gaussian curvature. We derive sharp Korn's first (linear geometric rigidity estimate) and second inequalities on that kind of shell for zero or periodic Dirichlet, Neumann, and Robin type boundary conditions. ...

Springer Verlag2017

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

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

An Efficient Streaming Algorithm for the Submodular Cover Problem

Volkan Cevher, Ilija Bogunovic, Ya-Ping Hsieh, Ashkan Norouzi Fard, Abbas Bazzi, Marwa El Halabi

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

2016

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

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

Robust Maximization of Non-Submodular Objectives

Graph Chatbot

Chat with Graph Search

Robustness via curvature regularization, and vice versa

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Maximizing Symmetric Submodular Functions

Gaussian Curvature as an Identifier of Shell Rigidity

A Distributed Algorithm for Partitioned Robust Submodular Maximization

A New Framework for Distributed Submodular Maximization

An Efficient Streaming Algorithm for the Submodular Cover Problem

Maximizing k-Submodular Functions and Beyond

Approximation algorithms for geometric dispersion

Robustness via curvature regularization, and vice versa

Maximizing Symmetric Submodular Functions

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Gaussian Curvature as an Identifier of Shell Rigidity

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

An Efficient Streaming Algorithm for the Submodular Cover Problem

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Maximizing k-Submodular Functions and Beyond

Approximation algorithms for geometric dispersion

A New Framework for Distributed Submodular Maximization