Randomized metarounding (extended abstract)

DOI10.1145/335305.335312MaRDI QIDQ3191971zbMATH OpenOpenAlexFDO

Authors

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335312

zbMATH Keywords

integrality gappolyhedrarandomized rounding

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Randomized metarounding
• On dependent randomized rounding algorithms
• scientific article; zbMATH DE number 1405893
• Improved Approximation Guarantees for Packing and Covering Integer Programs
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs

Cited in

(12)

• On minimizing the maximum congestion for weighted hypergraph embedding in a cycle
• Packing trees in communication networks
• A simple and fast algorithm for convex decomposition in relax-and-round mechanisms
• Truthfulness in advertising? Approximation mechanisms for knapsack bidders
• Generalized assignment problem: truthful mechanism design without money
• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
• Greedy algorithms for online survivable network design
• Fast approximation of minimum multicast congestion – Implementation VERSUS Theory
• Minimizing latency of capacitated \(k\)-tours
• Approximation algorithms for general packing problems and their application to the multicast congestion problem
• On routing in VLSI design and communication networks

This page was built for publication: Randomized metarounding (extended abstract)

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