Browsing by Author "Lücking, T."
Now showing items 112 of 12

Article
Computing Nash equilibria for scheduling on restricted parallel links
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2010)We consider the problem of routing nusers on m parallel links under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. So, this problem is equivalent to the ...

Conference Object
Computing Nash equilibria for scheduling on restricted parallel links
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2004)We consider the problem of routing n users on m parallel links, under the restriction that each user may only be routed on a link from a certain set of allowed links for the user. Thus, the problem is equivalent to the ...

Article
Nash equilibria in discrete routing games with convex latency functions
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2004)We study Nash equilibria in a discrete routing game that combines features of the two most famous models for noncooperative routing, the KP model [16] and the Wardrop model [27]. In our model, users share parallel links. ...

Article
Nash equilibria in discrete routing games with convex latency functions
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2008)In a discrete routing game, each of n selfish users employs a mixed strategy to ship her (unsplittable) traffic over m parallel links. The (expected) latency on a link is determined by an arbitrary nondecreasing, nonconstant ...

Article
A new model for selfish routing
Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2008)In this work, we introduce and study a new, potentially rich model for selfish routing over noncooperative networks, as an interesting hybridization of the two prevailing such models, namely the KPmodel [E. Koutsoupias, ...

Article
A new model for selfish routing
Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M. (2004)In this work, we introduce and study a new model for selfish routing over noncooperative networks that combines features from the two such best studied models, namely the KP model and the Wardrop model in an interesting ...

Article
The price of anarchy for polynomial social cost
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2006)In this work, we consider an interesting variant of the well studied KP model for selfish routing on parallel links, which reflects some influence from the much older Wardrop model [J.G. Wardrop, Some theoretical aspects ...

Article
The price of anarchy for polynomial social cost
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2004)In this work, we consider an interesting variant of the wellstudied KP model [18] for selfish routing that reflects some influence from the much older Wardrop model [31]. In the new model, user traffics are still unsplittable, ...

Article
The Price of Anarchy for restricted parallel links
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2006)In the model of restricted parallel links, n users must be routed on m parallel links under the restriction that the link for each user be chosen from a certain set of allowed links for the user. In a (pure) Nash equilibrium, ...

Article
A simple graphtheoretic model for selfish restricted scheduling
Elsässer, R.; Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard (2005)In this work, we introduce and study a simple, graphtheoretic model for selfish scheduling among m noncooperative users over a collection of n machines

Article
Structure and complexity of extreme Nash equilibria
Gairing, M.; Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Spirakis, Paul G. (2005)We study extreme Nash equilibria in the context of a selfish routing game. Specifically, we assume a collection of n users, each employing a mixed strategy, which is a probability distribution over m parallel identical ...

Article
Which is the worstcase Nash equilibrium?
Lücking, T.; Mavronicolas, Marios; Monien, Burkhard; Rode, M.; Spirakis, Paul G.; Vrto, I. (2003)A Nash equilibrium of a routing network represents a stable state of the network where no user finds it beneficial to unilaterally deviate from its routing strategy. In this work, we investigate the structure of such ...