Yannakakis M.

M. Yannakakis

Information about the author M. Yannakakis will soon be added to the site.
Found 7 papers in total
Perfect packing theorems and the average-case behavior of optimal and online bin packing
Perfect packing theorems and the average-case behavior of optimal and online bin packing
2002
We consider the one-dimensional bin packing problem under the discrete uniform...
On the hardness of approximating minimization problems
On the hardness of approximating minimization problems
1994
We prove results indicating that it is hard to compute efficiently good approximate...
Primal–dual approximation algorithms for integral flow and multicut in trees
Primal–dual approximation algorithms for integral flow and multicut in trees
1997
We study the maximum integral multicommodity flow problem and the minimum multicut...
Suboptimal cuts – their enumeration, weight and number
Suboptimal cuts – their enumeration, weight and number
1992
We present (1) an algorithm that enumerates the cuts of a network by increasing weight...
Shortest paths without a map
Shortest paths without a map
1991
We study several versions of the shortest-path problem when the map is not known in...
Simple local search problems that are hard to solve
Simple local search problems that are hard to solve
1991
Many algorithms for NP-hard optimization problems find solutions that are locally...
Batch sizing and job sequencing on a single machine
Batch sizing and job sequencing on a single machine
1990
The authors study a single-machine scheduling problem in which the items to be...
Papers per page: