On dependent randomized rounding algorithms

DOI10.1016/S0167-6377(99)00010-3zbMATH Open0954.90025MaRDI QIDQ1306458FDOQ1306458

Authors: Dimitris Bertsimas, Chung-Piaw Teo, Rakesh V. Vohra 

Publication date: 9 February 2001

Published in: Operations Research Letters (Search for Journal in Brave)

Recommendations

• Dependent rounding and its applications to approximation algorithms
• Geometric rounding: A dependent randomized rounding scheme
• scientific article; zbMATH DE number 2079377
• Publication:4938889

zbMATH Keywords

approximation algorithmsrandomized roundinground fractional solution to 0-1 solution

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09)

Cites Work

• Title not available (Why is that?)
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• An approximation algorithm for the generalized assignment problem
• Title not available (Why is that?)
• Bin packing can be solved within 1+epsilon in linear time
• The geometry of graphs and some of its algorithmic applications
• The Minimum Satisfiability Problem
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Rounding algorithms for covering problems
• Unimodular functions
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (30)

• Dependent Randomized Rounding: The Bipartite Case
• Scheduling on unrelated machines under tree-like precedence constraints
• A primal-dual approximation algorithm for \textsc{minsat}
• Randomized Rounding in the Presence of a Cardinality Constraint
• Geometric rounding: A dependent randomized rounding scheme
• Nonindependent Randomized Rounding and an Application to Digital Halftoning
• Approximation algorithms for supply chain planning and logistics problems with market choice
• Title not available (Why is that?)
• Rounding to an integral program
• Dual parameterization and parameterized approximability of subset graph problems
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Combinatorial randomized rounding: Boosting randomized rounding with combinatorial arguments
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Heuristics for the dynamic facility location problem with modular capacities
• On the Minimum Hitting Set of Bundles Problem
• Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Revisiting maximum satisfiability and related problems in data streams
• Minimum hitting set of interval bundles problem: computational complexity and approximability
• On the minimum hitting set of bundles problem
• A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem
• The enemy of my enemy is my friend: new conditions for network games
• Revisiting maximum satisfiability and related problems in data streams
• Randomized rounding in the presence of a cardinality constraint
• Solving the maximum duo-preservation string mapping problem with linear programming
• Randomized metarounding
• Dependent rounding and its applications to approximation algorithms

This page was built for publication: On dependent randomized rounding algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306458)