Deterministic algorithms for submodular maximization problems

DOI10.1137/1.9781611974331.CH29MaRDI QIDQ4575606zbMATH OpenOpenAlexFDO

Authors Niv Buchbinder, Moran Feldman

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974331.ch29

Mathematics Subject Classification ID

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

Recommendations

• Deterministic Algorithms for Submodular Maximization Problems
• Derandomization for k-submodular maximization
• Maximizing Non-monotone Submodular Functions
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid

Cited in

(17)

• Derandomization for k-submodular maximization
• On extensions of the deterministic online model for bipartite matching and max-sat
• Robust monotone submodular function maximization
• Restricted strong convexity implies weak submodularity
• Deterministic algorithms for the hidden subgroup problem
• Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
• Local search algorithms for the maximum carpool matching problem
• Deterministic Algorithms for Submodular Maximization Problems
• An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
• scientific article; zbMATH DE number 7255156 (Why is no real title available?)
• Generalized assignment via submodular optimization with reserved capacity
• Structured Robust Submodular Maximization: Offline and Online Algorithms
• Submodular Maximization Through the Lens of Linear Programming
• Local search algorithms for the maximum carpool matching problem
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Improved randomized algorithm for k-submodular function maximization
• Deterministic algorithms for multi-criteria max-TSP

This page was built for publication: Deterministic algorithms for submodular maximization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575606)