6 citations · 32 across the 37 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
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…
cs.GT2015★ 6 cited
Who to Trust for Truthfully Maximizing Welfare?
Dimitris Fotakis, Christos Tzamos, Emmanouil Zampetakis
We introduce a general approach based on \emph{selective verification} and obtain approximate mechanisms without money for maximizing the social welfare in the general domain of ut…