Publication

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.

Band Gap Renormalization at Different Symmetry Points in Perovskites

Majed Chergui, Lijie Wang

Using ultrafast broad-band transient absorption (TA) spectroscopy of photoexcited MAPbBr3 thin films with probe continua in the visible and the mid- to deep-ultraviolet (UV) ranges, we capture the ultrafast renormalization at the fundamental gap at the R s ...

Amer Chemical Soc2024

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Online Contention Resolution Schemes With Applications To Bayesian Selection Problems

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen

We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution schemes, a technique initially introduced in the context of submodular function maximization. Our rounding technique, which we call o ...

2021

Modified snaking in plane Couette flow with wall-normal suction

Tobias Schneider, Sajjad Azimi

A specific family of spanwise-localised invariant solutions of plane Couette flow exhibits homoclinic snaking, a process by which spatially localised invariant solutions of a nonlinear partial differential equation smoothly grow additional structure at the ...

2021

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen, Ashkan Norouzi Fard

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model t ...

ASSOC COMPUTING MACHINERY2020

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

Robust Maximization of Non-Submodular Objectives

Volkan Cevher, Ilija Bogunovic, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exi ...

2018

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

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

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