Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine
 
Loading...
Thumbnail Image
conference paper

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Rohwedder, Lars  
•
Wiese, Andreas
January 1, 2021
Stoc '21: Proceedings Of The 53Rd Annual Acm Sigact Symposium On Theory Of Computing
53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions.

The input consists of a set of jobs, characterized by their processing times, release times, and weights and we want to compute a (possibly preemptive) schedule for them. The objective is to minimize the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its release date and its completion time.

It had been a long-standing open problem to find a polynomial time O(1)-approximation algorithm for this setting. In a recent break-through result, Batra, Garg, and Kumar (FOCS 2018) found such an algorithm if the input data are polynomially bounded integers, and Feige, Kulkarni, and Li (SODA 2019) presented a black-box reduction to this setting. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this ratio to 2 + epsilon. The algorithm by Batra, Garg, and Kumar (FOCS 2018) reduces the problem to DEMAND MULTICUT ON TREES and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1 + epsilon, and then solve its resulting instances up to a factor of 2 + epsilon by a dynamic program. In particular, our reduction ensures certain structural properties, thanks to which we do not need LP-rounding methods.

We believe that our result makes substantial progress towards finding a PTAS for weighted flow time on a single machine.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3406325.3451075
Web of Science ID

WOS:000810492500093

Author(s)
Rohwedder, Lars  
•
Wiese, Andreas
Date Issued

2021-01-01

Publisher

ASSOC COMPUTING MACHINERY

Publisher place

New York

Journal
Stoc '21: Proceedings Of The 53Rd Annual Acm Sigact Symposium On Theory Of Computing
ISBN of the book

978-1-4503-8053-9

Series title/Series vol.

Annual ACM Symposium on Theory of Computing

Start page

1042

End page

1055

Subjects

Computer Science, Theory & Methods

•

Operations Research & Management Science

•

Mathematics, Applied

•

Computer Science

•

Mathematics

•

scheduling

•

approximation algorithm

•

dynamic programming

Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Event nameEvent placeEvent date
53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

ELECTR NETWORK

Jun 21-25, 2021

Available on Infoscience
July 18, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/189285
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés