Makespan minimization in no-wait flow shops: A polynomial time approximation scheme

M. Sviridenko

doi:10.1137/S0895480100370803

SIAM Journal on Discrete Mathematics

Paper

01 Feb 2003

Makespan minimization in no-wait flow shops: A polynomial time approximation scheme

View publication

Abstract

We investigate the approximability of a no-wait permutation flow shop scheduling problem under the makespan criterion. We present a polynomial time approximation scheme (PTAS) for the problem on any fixed number of machines.

Paper

Best possible approximation algorithm for MAX SAT with cardinality constraint

M. Sviridenko

Algorithmica (New York)

Conference paper

Online make-to-order joint replenishment model: Primal dual competitive algorithms

N. Buchbinder, T. Kimbrel, et al.

SODA 2008

Conference paper

Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs

H. Kaplan, M. Lewenstein, et al.

FOCS 2003

Paper

On the rate of convergence to the neutral attractor of a family of one-dimensional maps

T. Nowicki, M. Sviridenko, et al.

Fundamenta Mathematicae

View all publications

Abstract

Related

Best possible approximation algorithm for MAX SAT with cardinality constraint

Online make-to-order joint replenishment model: Primal dual competitive algorithms

Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs

On the rate of convergence to the neutral attractor of a family of one-dimensional maps