Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique (Q278736): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2016.04.005
+Normal rank
@@ Property / OpenAlex ID @@
+W2338410001
@@ Property / OpenAlex ID: W2338410001 / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time approximation algorithm for the weighted vertex cover problem
+Normal rank
@@ Property / cites work @@
+Q3221758
@@ Property / cites work: Q3221758 / rank @@
+Normal rank
@@ Property / cites work @@
+An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
+Normal rank
@@ Property / cites work @@
+On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
+Normal rank
@@ Property / cites work @@
+A note on the prize collecting traveling salesman problem
+Normal rank
@@ Property / cites work @@
+Q2768359
@@ Property / cites work: Q2768359 / rank @@
+Normal rank
@@ Property / cites work @@
+A primal-dual approximation algorithm for the facility location problem with submodular penalties
+Normal rank
@@ Property / cites work @@
+Q5684698
@@ Property / cites work: Q5684698 / rank @@
+Normal rank
@@ Property / cites work @@
+A push-relabel framework for submodular function minimization and applications to parametric optimization
+Normal rank
@@ Property / cites work @@
+Submodular functions and optimization.
@@ Property / cites work: Submodular functions and optimization. / rank @@
+Normal rank
@@ Property / cites work @@
+Capacitated vertex covering
@@ Property / cites work: Capacitated vertex covering / rank @@
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization
+Normal rank
@@ Property / cites work @@
+A General Approximation Technique for Constrained Forest Problems
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for the Set Covering and Vertex Cover Problems
+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 @@
+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 @@
+A better approximation ratio for the vertex cover problem
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty
+Normal rank
@@ Property / cites work @@
+Q3682236
@@ Property / cites work: Q3682236 / rank @@
+Normal rank
@@ Property / cites work @@
+A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
+Normal rank