Browsing by Author "Gairing, M."

Now showing items 1-10 of 10

    • 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  

      Extreme Nash equilibria 

      Gairing, M.; Lucking, T.; Mavronicolas, Marios; Monien, Burkhard; Spirakis, Paul G. (2003)
      We study the combinatorial structure and computational complexity of extreme Nash equilibria, ones that maximize or minimize a certain objective function, in the context of a selfish routing game. Specifically, we assume ...
    • 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 non-cooperative 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 non-decreasing, non-constant ...
    • 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 well-studied 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 graph-theoretic 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, graph-theoretic model for selfish scheduling among m non-cooperative 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 ...