Submodular Approximation: Sampling-based Algorithms and Lower Bounds

DOI10.1137/100783352zbMath1234.68468arXiv0805.1071OpenAlexW1967051853MaRDI QIDQ3225170

Zoya Svitkina, Lisa K. Fleischer

Publication date: 15 March 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0805.1071

zbMATH Keywords

approximation algorithmssubmodular functionsinformation-theoretic lower bounds

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (25)

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ Multi-attribute based influence maximization in social networks: algorithms and analysis ⋮ The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ A polyhedral approach to bisubmodular function minimization ⋮ Algorithms for maximizing monotone submodular function minus modular function under noise ⋮ Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints ⋮ Unnamed Item ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Activity preserving graph simplification ⋮ Influence maximization in the presence of vulnerable nodes: a ratio perspective ⋮ Submodular Function Minimization under a Submodular Set Covering Constraint ⋮ Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm ⋮ Submodular Cost Allocation Problem and Applications ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ Polyhedral results for a class of cardinality constrained submodular minimization problems ⋮ Robust budget allocation via continuous submodular functions ⋮ A note on submodular function minimization with covering type linear constraints ⋮ Optimizing network topology for average controllability ⋮ Set function optimization ⋮ An exact cutting plane method for \(k\)-submodular function maximization ⋮ Multi-dimensional vector assignment problems ⋮ Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings ⋮ New approximations and hardness results for submodular partitioning problems

This page was built for publication: Submodular Approximation: Sampling-based Algorithms and Lower Bounds