All reports by Author Marco Cesati:

__
TR00-080
| 24th July 2000
__

Marco Cesati#### Perfect Code is W[1]-complete

__
TR97-006
| 31st January 1997
__

Marco Cesati, Miriam Di Ianni#### Parameterized Parallel Complexity

Comments: 1

__
TR97-001
| 8th January 1997
__

Marco Cesati, Luca Trevisan#### On the Efficiency of Polynomial Time Approximation Schemes

Marco Cesati

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 >>>

Marco Cesati, Miriam Di Ianni

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 >>>

Marco Cesati, Luca Trevisan

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 >>>