dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.author | Monien, Burkhard | en |
dc.creator | Mavronicolas, Marios | en |
dc.creator | Monien, Burkhard | en |
dc.date.accessioned | 2019-11-13T10:41:13Z | |
dc.date.available | 2019-11-13T10:41:13Z | |
dc.date.issued | 2015 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/54508 | |
dc.description.abstract | We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. We extend this class to mix-weighted congestion games on parallel links, where weights may as well be negative. For the resulting simple class, we study the complexity of deciding the existence of a pure equilibrium, where no player could unilaterally improve her cost by switching to another link. We show that even for a single negative weight, this decision problem is strongly NP-complete when the number of links is part of the input | en |
dc.description.abstract | the problem is NP-complete already for two links. When the number of links is a fixed constant, we show, through a pseudopolynomial, dynamic programming algorithm, that the problem is not strongly NP-complete unless P=NP | en |
dc.description.abstract | the algorithm works for any number of negative weights. © 2015 Elsevier B.V. Allrightsreserved. | en |
dc.source | Information Processing Letters | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84938875810&doi=10.1016%2fj.ipl.2015.07.012&partnerID=40&md5=b879cb16745ad4091e893605fb904595 | |
dc.subject | Dynamic programming | en |
dc.subject | Algorithms | en |
dc.subject | Non negatives | en |
dc.subject | Polynomials | en |
dc.subject | NP Complete | en |
dc.subject | Decision problems | en |
dc.subject | Parallel links | en |
dc.subject | Congestion Games | en |
dc.subject | Congestion games on parallel links | en |
dc.subject | Dynamic programming algorithm | en |
dc.subject | NP-completeness | en |
dc.subject | Pure equilibria | en |
dc.title | The complexity of pure equilibria in mix-weighted congestion games on parallel links | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1016/j.ipl.2015.07.012 | |
dc.description.volume | 115 | |
dc.description.issue | 12 | |
dc.description.startingpage | 927 | |
dc.description.endingpage | 931 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.source.abbreviation | Inf.Process.Lett. | en |