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

@@ Property / DOI @@
-.1016/j.tcs.2016.04.005
@@ Property / DOI: 10.1016/j.tcs.2016.04.005 / rank @@
-Normal rank
@@ Property / author @@
-Da-Chuan Xu
@@ Property / author: Da-Chuan Xu / rank @@
-Normal rank
@@ Property / author @@
-Dong-lei Du
@@ Property / author: Dong-lei Du / rank @@
-Normal rank
@@ Property / author @@
-Chen-Chen Wu
@@ Property / author: Chen-Chen Wu / rank @@
-Normal rank
@@ Property / author @@
+Da-Chuan Xu
@@ Property / author: Da-Chuan Xu / rank @@
+Normal rank
@@ Property / author @@
+Dong-lei Du
@@ Property / author: Dong-lei Du / rank @@
+Normal rank
@@ Property / author @@
+Chen-Chen Wu
@@ Property / author: Chen-Chen Wu / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C59
@@ Property / Mathematics Subject Classification ID: 90C59 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C70
@@ Property / Mathematics Subject Classification ID: 05C70 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+W25
@@ Property / Mathematics Subject Classification ID: 68W25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C27
@@ Property / Mathematics Subject Classification ID: 90C27 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C35
@@ Property / Mathematics Subject Classification ID: 90C35 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6576261
@@ Property / zbMATH DE Number: 6576261 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+penalty
@@ Property / zbMATH Keywords: penalty / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+submodular vertex cover
@@ Property / zbMATH Keywords: submodular vertex cover / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+primal-dual approximation algorithm
@@ Property / zbMATH Keywords: primal-dual approximation algorithm / rank @@
+Normal rank
@@ 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.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
@@ Property / DOI @@
+.1016/J.TCS.2016.04.005
@@ Property / DOI: 10.1016/J.TCS.2016.04.005 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:278736