2 Search Results for "Soper, Alan J."

Document

DOI: 10.4230/LIPIcs.WADS.2025.25

An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines

Authors: Leah Epstein and Asaf Levin

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

We study a classic scheduling problem on uniformly related machines for which we show an efficient polynomial time approximation scheme (EPTAS), where an EPTAS is a fast and practical approximation scheme. For a desired approximation ratio of 1+ε for ε > 0, the running time of an EPTAS is a function of ε multiplied by a polynomial function of the input length. New methods and techniques are essential in developing such improved approximation schemes, and their design is a primary goal of this research agenda. We present an EPTAS for the scheduling problem of a set of jobs on uniformly related machines so as to minimize the total weighted completion time. The problem is NP-hard in the strong sense, and therefore an EPTAS is the best possible approximation scheme for the problem, unless P=NP. Prior to our work, only a PTAS was known for the problem, while an EPTAS was known only for the special case of identical machines.

Cite as

Leah Epstein and Asaf Levin. An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 25:1-25:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:LIPIcs.WADS.2025.25,
  author =	{Epstein, Leah and Levin, Asaf},
  title =	{{An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{25:1--25:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.25},
  URN =		{urn:nbn:de:0030-drops-242564},
  doi =		{10.4230/LIPIcs.WADS.2025.25},
  annote =	{Keywords: Scheduling algorithms, Approximation schemes, Min-sum objective}
}

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.392

Power of Preemption on Uniform Parallel Machines

Authors: Alan J. Soper and Vitaly A. Strusevich

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract

For a scheduling problem on parallel machines, the power of preemption is defined as the ratio of the makespan of an optimal non-preemptive schedule over the makespan of an optimal preemptive schedule. For m uniform parallel machines, we give the necessary and sufficient conditions under which the global bound of 2-1/m is tight. If the makespan of the optimal preemptive schedule is defined by the ratio of the total processing times of r < m longest jobs over the total speed of r fastest machines, we show that the tight bound on the power of preemption is 2-1/min{r,m-r}.

Cite as

Alan J. Soper and Vitaly A. Strusevich. Power of Preemption on Uniform Parallel Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 392-402, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{soper_et_al:LIPIcs.APPROX-RANDOM.2014.392,
  author =	{Soper, Alan J. and Strusevich, Vitaly A.},
  title =	{{Power of Preemption on Uniform Parallel Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{392--402},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.392},
  URN =		{urn:nbn:de:0030-drops-47116},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.392},
  annote =	{Keywords: Machine Scheduling, Uniform Parallel Machines, Power of Preemption}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2014

Refine by Author
1 Epstein, Leah
1 Levin, Asaf
1 Soper, Alan J.
1 Strusevich, Vitaly A.

Refine by Series/Journal
2 LIPIcs

Refine by Classification
1 Theory of computation → Scheduling algorithms

Refine by Keyword
1 Approximation schemes
1 Machine Scheduling
1 Min-sum objective
1 Power of Preemption
1 Scheduling algorithms
Show More...

2 Search Results for "Soper, Alan J."

An Efficient Polynomial Time Approximation Scheme for Minimizing the Total Weighted Completion Time on Uniformly Related Machines

Abstract

Cite as

Power of Preemption on Uniform Parallel Machines

Abstract

Cite as

Thanks for your feedback!

Could not send message