Partial Resampling to Approximate Covering Integer Programs (Q4575724): Difference between revisions

← Older edit

@@ Property / title @@
+Partial resampling to approximate covering integer programs† (English)
+Normal rank
@@ Property / zbMATH Open document ID @@
+.68754
@@ Property / zbMATH Open document ID: 1522.68754 / rank @@
+Normal rank
@@ Property / DOI @@
+.1002/rsa.20964
@@ Property / DOI: 10.1002/rsa.20964 / rank @@
+Normal rank
@@ Property / published in @@
+Random Structures &amp; Algorithms
@@ Property / published in: Random Structures & Algorithms / rank @@
+Normal rank
@@ Property / publication date @@
+October 2023Timestamp +2023-10-11T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2023-10-11T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 11 October 2023 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+W20
@@ Property / Mathematics Subject Classification ID: 68W20 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C27
@@ Property / Mathematics Subject Classification ID: 90C27 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+7748477
@@ Property / zbMATH DE Number: 7748477 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+approximation algorithms
@@ Property / zbMATH Keywords: approximation algorithms / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+integer programming
@@ Property / zbMATH Keywords: integer programming / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+randomized rounding
@@ Property / zbMATH Keywords: randomized rounding / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+set cover
@@ Property / zbMATH Keywords: set cover / rank @@
+Normal rank
@@ Property / cites work @@
+Q3191563
@@ Property / cites work: Q3191563 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved lower bounds on <i>k</i>‐independence
@@ Property / cites work: Improved lower bounds on <i>k</i>‐independence / rank @@
+Normal rank
@@ Property / cites work @@
+Q4952606
@@ Property / cites work: Q4952606 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4607903
@@ Property / cites work: Q4607903 / rank @@
+Normal rank
@@ Property / cites work @@
+On Approximating (Sparse) Covering Integer Programs
+Normal rank
@@ Property / cites work @@
+Approximation hardness of dominating set problems in bounded degree graphs
+Normal rank
@@ Property / cites work @@
+A Greedy Heuristic for the Set-Covering Problem
@@ Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
+Normal rank
@@ Property / cites work @@
+Q4074927
@@ Property / cites work: Q4074927 / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+On the Greedy Heuristic for Continuous Covering and Packing Problems
+Normal rank
@@ Property / cites work @@
+Lopsidependency in the Moser-Tardos Framework
@@ Property / cites work: Lopsidependency in the Moser-Tardos Framework / rank @@
+Normal rank
@@ Property / cites work @@
+The Moser--Tardos Framework with Partial Resampling
+Normal rank
@@ Property / cites work @@
+A note on the discrepancy of matrices with bounded row and column sums
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for covering/packing integer programs
+Normal rank
@@ Property / cites work @@
+New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning
+Normal rank
@@ Property / cites work @@
+On the ratio of optimal integral and fractional covers
+Normal rank
@@ Property / cites work @@
+A constructive proof of the general lovász local lemma
+Normal rank
@@ Property / cites work @@
+Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
+Normal rank
@@ Property / cites work @@
+Randomized rounding: A technique for provably good algorithms and algorithmic proofs
+Normal rank
@@ Property / cites work @@
+A Tight Analysis of the Greedy Algorithm for Set Cover
+Normal rank
@@ Property / cites work @@
+An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
+Normal rank
@@ Property / cites work @@
+Non-approximability results for optimization problems on bounded degree instances
+Normal rank
@@ Property / cites work @@
+Q4598189
@@ Property / cites work: Q4598189 / rank @@
+Normal rank