Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Marco Cesati:

TR00-080 | 24th July 2000
Marco Cesati

Perfect Code is W[1]-complete

We show that the parameterized problem Perfect Code belongs to W[1].
This result closes an old open question, because it was often
conjectured that Perfect Code could be a natural problem having
complexity degree intermediate between W[1] and W[2]. This result
also shows W[1]-membership of the parameterized problem Weighted
more >>>

TR97-006 | 31st January 1997
Marco Cesati, Miriam Di Ianni

Parameterized Parallel Complexity

Comments: 1

We consider the framework of Parameterized Complexity, and we
investigate the issue of which problems do admit efficient fixed
parameter parallel algorithms by introducing two different
degrees of efficiently parallelizable parameterized problems, PNC
and FPP. We sketch both some FPP-algorithms solving natural
parameterized problems and ... more >>>

TR97-001 | 8th January 1997
Marco Cesati, Luca Trevisan

On the Efficiency of Polynomial Time Approximation Schemes

A polynomial time approximation scheme (PTAS) for an optimization
problem $A$ is an algorithm that on input an instance of $A$ and
$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time
that is polynomial for each fixed $\epsilon$. Typical running times
are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ... more >>>

ISSN 1433-8092 | Imprint