The construction of perfect hash functions is a well-studied topic. In this article, this concept is generalized with the following definition. We say that a family of functions from [ n ] to [ k ] is a δ-balanced ( n,k )-family of perfect hash functions if for every S ⊆ [ n ], | S |= k , the number of functions that are 1-1 on S is between T /δ and δ T for some constant T >0. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on S , for each S of size k . In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking δ to be close to 1) for every such S . Our main result is that for any constant δ > 1, a δ-balanced ( n,k )-family of perfect hash functions of size 2 O ( k log log k ) log n can be constructed in time 2 O ( k log log k ) n log n . Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial-time algorithm for approximating both the number of simple paths of length k and the number of simple cycles of size k for any k ≤ O (log n /log log log n ) in a graph with n vertices. The approximation is up to any fixed desirable relative error.

The unsplittable flow problem is one of the most extensively studied optimization problems in the field of networking. An instance of it consists of an edge capacitated graph and a set of connection requests, each of which is associated with source and target vertices, a demand, and a value. The objective is to route a maximum value subset of requests subject to the edge capacities. It is a well known fact that as the capacities of the edges are larger with respect to the maximal demand among the requests, the problem can be approximated better. In particular, it is known that for sufficiently large capacities, the integrality gap of the corresponding integer linear program becomes 1 + ϵ, which can be matched by an algorithm that utilizes the randomized rounding technique. In this article, we focus our attention on the large capacities unsplittable flow problem in a game theoretic setting. In this setting, there are selfish agents, which control some of the requests characteristics, and may be dishonest about them. It is worth noting that in game theoretic settings many standard techniques, such as randomized rounding, violate certain monotonicity properties, which are imperative for truthfulness, and therefore cannot be employed. In light of this state of affairs, we design a monotone deterministic algorithm, which is based on a primal-dual machinery, which attains an approximation ratio of e / e -1, up to a disparity of ϵ away. This implies an improvement on the current best truthful mechanism, as well as an improvement on the current best combinatorial algorithm for the problem under consideration. Surprisingly, we demonstrate that any algorithm in the family of reasonable iterative path minimizing algorithms, cannot yield a better approximation ratio. Consequently, it follows that in order to achieve a monotone PTAS, if that exists, one would have to exert different techniques. We also consider the large capacities single-minded multi-unit combinatorial auction problem . This problem is closely related to the unsplittable flow problem since one can formulate it as a special case of the integer linear program of the unsplittable flow problem. Accordingly, we obtain a comparable performance guarantee by refining the algorithm suggested for the unsplittable flow problem.

We study the admission control problem in general networks. Communication requests arrive over time, and the online algorithm accepts or rejects each request while maintaining the capacity limitations of the network. The admission control problem has been usually analyzed as a benefit problem, where the goal is to devise an online algorithm that accepts the maximum number of requests possible. The problem with this objective function is that even algorithms with optimal competitive ratios may reject almost all of the requests, when it would have been possible to reject only a few. This could be inappropriate for settings in which rejections are intended to be rare events. In this article, we consider preemptive online algorithms whose goal is to minimize the number of rejected requests. Each request arrives together with the path it should be routed on. We show an O (log 2 ( mc ))-competitive randomized algorithm for the weighted case, where m is the number of edges in the graph and c is the maximum edge capacity. For the unweighted case, we give an O (log m log c )-competitive randomized algorithm. This settles an open question of Blum et al. [2001]. We note that allowing preemption and handling requests with given paths are essential for avoiding trivial lower bounds. The admission control problem is a generalization of the online set cover with repetitions problem, whose input is a family of m subsets of a ground set of n elements. Elements of the ground set are given to the online algorithm one by one, possibly requesting each element a multiple number of times. (If each element arrives at most once, this corresponds to the online set cover problem.) The algorithm must cover each element by different subsets, according to the number of times it has been requested. We give an O (log m log n )-competitive randomized algorithm for the online set cover with repetitions problem. This matches a recent lower bound of Ω(log m log n ) given by Korman [2005] (based on Feige [1998]) for the competitive ratio of any randomized polynomial time algorithm, under the BPP ≠ NP assumption. Given any constant ϵ > 0, an O (log m log n )-competitive deterministic bicriteria algorithm is shown that covers each element by at least (1 - ϵ) k sets, where k is the number of times the element is covered by the optimal solution.

The unsplittable flow problem is one of the most extensively studied optimization problems in the field of networking. An instance of it consists of an edge capacitated graph and a set of connection requests, each of which is associated with source and target vertices, a demand, and a value. The objective is to route a maximum value subset of requests subject to the edge capacities. It is a well known fact that as the capacities of the edges are larger with respect to the maximal demand among the requests, the problem can be approximated better. In particular, it is known that for sufficiently large capacities, the integrality gap of the corresponding integer linear program becomes 1+ε, which can be matched by an algorithm that utilizes the randomized rounding technique.

Abstract We study the admission control problem in general networks. Communication requests arrive overtime, and the online algorithm accepts or rejects each request while maintaining the capacity limitations of the network. The admission control problem has been usually analyzed as a benefit problem, where thegoal is to devise an online algorithm that accepts the maximum number of requests possible. The problem with this objective function is that even algorithms with optimal competitive ratios may reject almost allof the requests, when it would have been possible to reject only a few. This could be inappropriate for settings in which rejections are intended to be rare events.In this paper, we consider preemptive online algorithms whose goal is to minimize the number of rejected requests. Each request arrives together with the path it should be routed on. We show an O(log2(mc))-competitive randomized algorithm for the weighted case, where m is the number of edgesin the graph and c is the maximum edge capacity. For the unweighted case, we give an O(log m log c)-competitive randomized algorithm. This settles an open question of Blum, Kalai and Kleinberg raised in [10]. We note that allowing preemption and handling requests with given paths are essential for avoidingtrivial lower bounds. The admission control problem is a generalization of the online set cover with repetitions problem,whose input is a family of m subsets of a ground set of n elements. Elements of the ground set are givento the online algorithm one by one, possibly requesting each element a multiple number of times. (If each element arrives at most once, this corresponds to the online set cover problem.) The algorithm must covereach element by different subsets, according to the number of times it has been requested. We give an O(log m log n)-competitive randomized algorithm for the the online set cover with rep-etitions problem. This matches a recent lower bound of \\Omega (log m log n) given by Feige and Korman forthe competitive ratio of any randomized polynomial time algorithm, under the BP P 6 = N P assumption.Given any constant ffl> 0, we show an O(log m log n)-competitive deterministic bicriteria algorithm thatcovers each element by at least (1-