Randomized Rounding for Routing and Covering Problems: Experiments and\n Improvements

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