Abstract: We consider selfish routing over a network consisting of m parallellinks through which $n$ selfish users route their traffic trying tominimize their own expected latency. We study the class of mixedstrategies in which the expected latency through each link is at mosta constant multiple of the optimum maximum latency had globalregulation been available. For the case of uniform links it is knownthat all Nash equilibria belong to this class of strategies. We areinterested in bounding the coordination ratio (or price of anarchy) ofthese strategies defined as the worst-case ratio of the maximum (overall links) expected latency over the optimum maximum latency. The loadbalancing aspect of the problem immediately implies a lower boundO(ln m ln ln m) of the coordinationratio. We give a tight (up to a multiplicative constant) upper bound.To show the upper bound, we analyze a variant of the classical ballsandbinsproblem, in which balls with arbitrary weights are placedinto bins according to arbitrary probability distributions. At theheart of our approach is a new probabilistic tool that we call ballfusion; this tool is used to reduce the variant of the problem whereballs bear weights to the classical version (with no weights). Ballfusion applies to more general settings such as links with arbitrarycapacities and other latency functions.
Abstract: The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable
ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up
to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. In this paper,
we consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own
right. More specifically, we show how the method of local maximum satisfying truth assignments can be combined with results for
the occupancy problem in schemes of random allocation of balls into bins in order to achieve an upper bound for the unsatisfiability
threshold less than 4.571. In order to obtain this value, we establish a bound on the q-binomial coefficients (a generalization of the
binomial coefficients). No such bound was previously known, despite the extensive literature on q-binomial coefficients. Finally,
to prove our result we had to establish certain relations among the conditional probabilities of an event in various probabilistic
models for random formulas. It turned out that these relations were considerably harder to prove than the corresponding ones for
unconditional probabilities, which were previously known.