13 citations · 46 across the 31 of their papers we have counts for
Showing 2012 · cs.CCShow all
2 papers · 2 filters
cs.CC2012
Improved Inapproximability for TSP
Michael Lampis
The Traveling Salesman Problem is one of the most studied problems in computational complexity and its approximability has been a long standing open question. Currently, the best k…
cs.CC2012
Scrabble is PSPACE-Complete
Michael Lampis, Valia Mitsou, Karolina Sołtys
In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Eri…