Complexity and approximations for submodular minimization problems on two variables per inequality constraints (Q1801066): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.dam.2018.04.012
+Normal rank
@@ Property / OpenAlex ID @@
+W2800014321
@@ Property / OpenAlex ID: W2800014321 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Complexity of Timetable and Multicommodity Flow Problems
+Normal rank
@@ Property / cites work @@
+Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Efficient bounds for the stable set, vertex cover and set packing problems
+Normal rank
@@ Property / cites work @@
+Approximating Clique and Biclique Problems
@@ Property / cites work: Approximating Clique and Biclique Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
+Normal rank
@@ Property / cites work @@
+Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
+Normal rank
@@ Property / cites work @@
+Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
+Normal rank
@@ Property / cites work @@
+Minimizing a Convex Cost Closure Set
@@ Property / cites work: Minimizing a Convex Cost Closure Set / rank @@
+Normal rank
@@ Property / cites work @@
+A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
+Normal rank
@@ Property / cites work @@
+Submodular Function Minimization under Covering Constraints
+Normal rank
@@ Property / cites work @@
+Q4633938
@@ Property / cites work: Q4633938 / rank @@
+Normal rank
@@ Property / cites work @@
+The Minimum Satisfiability Problem
@@ Property / cites work: The Minimum Satisfiability Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
+Normal rank
@@ Property / cites work @@
+The Computational Complexity of Simultaneous Diophantine Approximation Problems
+Normal rank
@@ Property / cites work @@
+On approximation algorithms for the minimum satisfiability problem
+Normal rank
@@ Property / cites work @@
+A faster strongly polynomial time algorithm for submodular function minimization
+Normal rank
@@ Property / cites work @@
+A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1801066