Randomized rounding for routing and covering problems: experiments and improvements

DOI10.1007/978-3-642-13193-6_17zbMATH Open1434.68672arXiv1007.0372OpenAlexW1581948717MaRDI QIDQ3558348FDOQ3558348

Authors: Benjamin Doerr, Marvin Künnemann, Magnus Wahlström 

Publication date: 4 May 2010

Published in: Experimental Algorithms (Search for Journal in Brave)

Abstract: Following previous theoretical work by Srinivasan (FOCS 2001) and the first author (STACS 2006) and a first experimental evaluation on random instances (ALENEX 2009), we investigate how the recently developed different approaches to generate randomized roundings satisfying disjoint cardinality constraints behave when used in two classical algorithmic problems, namely low-congestion routing in networks and max-coverage problems in hypergraphs. We generally find that all randomized rounding algorithms work well, much better than what is guaranteed by existing theoretical work. The derandomized versions produce again significantly better rounding errors, with running times still negligible compared to the one for solving the corresponding LP. It thus seems worth preferring them over the randomized variants. The data created in these experiments lets us propose and investigate the following new ideas. For the low-congestion routing problems, we suggest to solve a second LP, which yields the same congestion, but aims at producing a solution that is easier to round. Experiments show that this reduces the rounding errors considerably, both in combination with randomized and derandomized rounding. For the max-coverage instances, we generally observe that the greedy heuristics also performs very good. We develop a strengthened method of derandomized rounding, and a simple greedy/rounding hybrid approach using greedy and LP-based rounding elements, and observe that both these improvements yield again better solutions than both earlier approaches on their own. For unit disk max-domination, we also develop a PTAS. Contrary to all other algorithms investigated, it performs not much better in experiments than in theory; thus, unless extremely good solutions are to be obtained with huge computational resources, greedy, LP-based rounding or hybrid approaches are preferable.

Full work available at URL: https://arxiv.org/abs/1007.0372

Recommendations

• Rounding algorithms for covering problems
• Generating Randomized Roundings with Cardinality Constraints and Derandomizations
• Dependent rounding and its applications to approximation algorithms
• Randomized Rounding in the Presence of a Cardinality Constraint
• Dependent Randomized Rounding: The Bipartite Case

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Deterministic network models in operations research (90B10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cited In (2)

• Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router
• Congestion minimization for multipath routing via multiroute flows

This page was built for publication: Randomized rounding for routing and covering problems: experiments and improvements

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