A simpler and better derandomization of an approximation algorithm for single source rent-or-buy

We present a very simple way of derandomizing the algorithm proposed by Gupta, Kumar and Roughgarden for single source rent-or-buy by using the method of conditional expectation. Using the improved analysis of Eisenbrand, Grandoni and Rothvoß, our derandomized algorithm has an approximation guarantee of 3.28.     

A derandomization using min-wise independent permutations

Min-wise independence is a recently introduced notion of limited independence, similar in spirit to pairwise independence. The latter has proven essential for the derandomization of many algorithms. Here we show that approximate min-wise independence allows similar uses, by presenting a derandomization of the RNC algorithm for approximate set cover due to S. Rajagopalan and V. Vazirani. We also discuss how to derandomize their set multi-cover and multi-set multi-cover algorithms in restricted cases. The multi-cover case leads us to discuss the concept of k-minima-wise independence, a natural counterpart to k-wise independence.     

An improved approximation algorithm for maximum edge 2-coloring in simple graphs

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of $\frac{468}{575}$. This improves on the previous best (trivial) ratio of $\frac{4}{5}$.     

Algorithmic construction of low-discrepancy point sets via dependent randomized rounding

We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on recent results on randomized roundings respecting hard constraints and their derandomization. It is structurally much simpler than a previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav, Bounds and constructions for the star discrepancy via δ$\delta$-covers, J. Complexity, 21 (2005) 691–709]. Besides leading to better theoretical running time bounds, our approach also can be implemented with reasonable effort. We implemented this algorithm and performed numerical comparisons with other known low-discrepancy constructions. The experiments take place in dimensions ranging from 5 to 21 and indicate that our algorithm leads to superior results if the dimension is relatively high and the number of points that have to be constructed is rather small.     

Reroute sequence planning in telecommunication networks and compact vector summation

The paper deals with the reroute sequence planning in telecommunication networks. Initially, we are given communication requests between terminal pairs and a path system which is able to satisfy these demands while respecting the physical link capacities. A reconfiguration problem arises when the path set is recalculated by a global optimization method for achieving a better resource utilization. After the recalculation the paths in the routing have to be changed to the optimized ones in the working network. In this case, a sequence of one by one reroutings have to be found with the constraint that the capacities should not be violated and no one of the demands can become unsatisfied during the reroute process. Provided that the (initial and final) free capacities are large enough, such a permutation can be computed. The paper deals with theoretical results giving bounds for these free capacities, with vector-sum and discrepancy methods.