6 citations · 32 across the 37 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2019
Node Max-Cut and Computing Equilibria in Linear Weighted Congestion Games
Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas +3
In this work, we seek a more refined understanding of the complexity of local optimum computation for Max-Cut and pure Nash equilibrium (PNE) computation for congestion games with…
cs.CC2015
Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse
Dimitris Fotakis, Michael Lampis, Vangelis Th. Paschos
It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS~99), that \MC\ admits a PTAS on dense graphs, and more generally, \kCSP\ admits a PTAS on "dense…