Randomized metarounding

DOI10.1002/RSA.10033MaRDI QIDQ4537626zbMATH OpenOpenAlexFDO

Authors

Publication date 1 July 2002

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://digital.library.unt.edu/ark:/67531/metadc704036/

zbMATH Keywords

approximation algorithmsheuristicinteger polytopelinear relaxation

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On dependent randomized rounding algorithms
• scientific article; zbMATH DE number 1405893
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• scientific article; zbMATH DE number 2077129

Cites work

• A guided tour of Chernoff bounds
• Multiterminal global routing: A deterministic approximation scheme
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs

Cited in

(31)

• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• New class of 0-1 integer programs with tight approximation via linear relaxations
• On the approximability of robust network design
• Stochastic makespan minimization in structured set systems
• Greedy algorithms for the profit-aware social team formation problem
• On fractional cut covers
• Hardness and approximation results for packing Steiner trees
• Approximating the least core value and least core of cooperative games with supermodular costs
• An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
• Iterative packing for demand and hypergraph matching
• Randomized metarounding (extended abstract)
• Analysis of randomised rounding for integer programs
• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Generalized hypergraph matching via iterated packing and local ratio
• Multicast Routing and Design of Sparse Connectors
• Thresholded covering algorithms for robust and max-min optimization
• Improved approximation algorithms for directed Steiner forest
• Algorithms as mechanisms: the price of anarchy of relax and round
• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Finding Sparse Solutions for Packing and Covering Semidefinite Programs
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
• Solving zero-sum games using best-response oracles with applications to search games
• The complexity of contracts
• Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations
• Resource time-sharing for IoT applications with deadlines
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Revisiting priority k-center: fairness and outliers
• Constant-factor approximation to deadline TSP and related problems in (almost) quasi-polytime
• Near-optimal schedules for simultaneous multicasts
• Improved lower bounds on multiflow-multicut gaps

This page was built for publication: Randomized metarounding

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