13 citations · 46 across the 31 of their papers we have counts for
4 papers · 1 filter
Complexity and Approximability of Parameterized MAX-CSPs
Holger Dell, Eun Jung Kim, Michael Lampis +2
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constr…
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…
Algorithmic Aspects of Upper Domination
Cristina Bazgan, Ljiljana Brankovic, Katrin Casel +6
In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a…
Time-Approximation Trade-offs for Inapproximable Problems
Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos
In this paper we focus on problems which do not admit a constant-factor approximation in polynomial time and explore how quickly their approximability improves as the allowed runni…