Luca Trevisan

We consider the Traveling Salesperson Problem (TSP) restricted

to Euclidean spaces of dimension at most k(n), where n is the number of

cities. We are interested in the relation between the asymptotic growth of

k(n) and the approximability of the problem. We show that the problem is ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

We design a polynomial time approximation scheme (PTAS) for

the problem of Metric MIN-BISECTION of dividing a given finite metric

space into two halves so as to minimize the sum of distances across

that partition. The method of solution depends on a new metric placement

partitioning ...
more >>>