Complexity and approximations for submodular minimization problems on two variables per inequality constraints

DOI10.1016/j.dam.2018.04.012zbMath1398.05200OpenAlexW2800014321MaRDI QIDQ1801066

Dorit S. Hochbaum

Publication date: 26 October 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.04.012

zbMATH Keywords

approximation algorithmssubmodular optimizationmonotone constraintssubmodular closure

Mathematics Subject Classification ID

Integer programming (90C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

A primal-dual approximation algorithm for \textsc{minsat}

Cites Work

• Unnamed Item
• A faster strongly polynomial time algorithm for submodular function minimization
• Efficient bounds for the stable set, vertex cover and set packing problems
• Geometric algorithms and combinatorial optimization
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• On approximation algorithms for the minimum satisfiability problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Approximating Clique and Biclique Problems
• The Minimum Satisfiability Problem
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Minimizing a Convex Cost Closure Set
• Submodular Function Minimization under Covering Constraints
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

This page was built for publication: Complexity and approximations for submodular minimization problems on two variables per inequality constraints