Browsing by Subject "NP-hard"

Now showing items 1-4 of 4

    • Article  

      Broadcast scheduling with multiple concurrent costs 

      Liaskos, Christos K.; Xeros, Andreas; Papadimitriou, Georgios I.; Lestas, Marios; Pitsillides, Andreas (2012)
      Data dissemination via periodic broadcasting considers a set of items, each with a given request probability, size and scheduling cost. The goal is to construct a broadcast schedule that minimizes the mean query serving ...
    • Article  

      Complexity of rational and irrational Nash equilibria 

      Bilò, Vittorio; Mavronicolas, Marios (2011)
      We introduce two new decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, ...
    • Article  

      Complexity of rational and irrational nash equilibria 

      Bilò, Vittorio; Mavronicolas, Marios (2014)
      We introduce two new natural decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ...
    • Article  

      Periodic scheduling with costs revisited: A novel approach for wireless broadcasting 

      Liaskos, Christos K.; Xeros, Andreas; Papadimitriou, Georgios I.; Lestas, Marios; Pitsillides, Andreas (2012)
      Periodic broadcast scheduling typically considers a set of discrete data items, characterized by their popularity, size and scheduling cost. A classic goal is the definition of an infinite, periodic schedule that yields ...