Show simple item record

dc.contributor.authorKoutsoupias, Eliasen
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorSpirakis, Paul G.en
dc.creatorKoutsoupias, Eliasen
dc.creatorMavronicolas, Mariosen
dc.creatorSpirakis, Paul G.en
dc.description.abstractWe consider selfish routing over a network consisting of m parallel links through which n selfish users route their traffic trying to minimize their own expected latency. We study the class of mixed strategies in which the expected latency through each link is at most a constant multiple of the optimum maximum latency had global regulation been available. For the case of uniform links it is known that all Nash equilibria belong to this class of strategies. We are interested in bounding the coordination ratio (or price of anarchy) of these strategies defined as the worst-case ratio of the maximum (over all links) expected latency over the optimum maximum latency. The load balancing aspect of the problem immediately implies a lower bound ω (ln m/ln ln m) of the coordination ratio. We give a tight (up to a multiplicative constant) upper bound. To show the upper bound, we analyze a variant of the classical balls and bins problem, in which balls with arbitrary weights are placed into bins according to arbitrary probability distributions. At the heart of our approach is a new probabilistic tool that we call ball fusionen
dc.description.abstractthis tool is used to reduce the variant of the problem where balls bear weights to the classical version (with no weights). Ball fusion applies to more general settings such as links with arbitrary capacities and other latency functions.en
dc.sourceTheory of Computing Systemsen
dc.subjectProblem solvingen
dc.subjectGame theoryen
dc.subjectApproximation theoryen
dc.subjectTelecommunication networksen
dc.subjectProbability distributionsen
dc.subjectParallel processing systemsen
dc.subjectTelecommunication trafficen
dc.subjectMultiobjective problemsen
dc.subjectSaddle-point equilibriumen
dc.titleApproximate Equilibria and Ball Fusionen
dc.description.endingpage693 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :76</p>en
dc.source.abbreviationTheory Comput.Syst.en
dc.contributor.orcidSpirakis, Paul G. [0000-0001-5396-3749]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record