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. Flow Time Scheduling and Prefix Beck-Fiala
 
conference paper

Flow Time Scheduling and Prefix Beck-Fiala

Bansal, Nikhil
•
Rohwedder, Lars
•
Svensson, Ola  
January 1, 2022
Proceedings Of The 54Th Annual Acm Sigact Symposium On Theory Of Computing (Stoc '22)
54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bounded iota 1-norm) setting to bounds on the flow time of an optimal schedule. Combining our reduction with a deep result proved by Banaszczyk via convex geometry, give guarantees of O(root logn) and O( root logn logp) for max flow time and total flow time, respectively, improving upon the previous best guarantees of O(logn) and O( log n log p). Apart from the improved guarantees, the reduction motivates seemingly easy versions of prefix discrepancy questions: any constant bound on prefix Beck-Fiala where vectors have sparsity two (sparsity one being trivial) would already yield tight guarantees for both max flow time and total flow time. While known techniques solve this case when the entries take values in {-1, 0, 1}, we show that they are unlikely to transfer to the more general 2-sparse case of bounded iota 1-norm.

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

WOS:000852709400029

Author(s)
Bansal, Nikhil
Rohwedder, Lars
Svensson, Ola  
Date Issued

2022-01-01

Publisher

ASSOC COMPUTING MACHINERY

Publisher place

New York

Published in
Proceedings Of The 54Th Annual Acm Sigact Symposium On Theory Of Computing (Stoc '22)
ISBN of the book

978-1-4503-9264-8

Series title/Series vol.

Annual ACM Symposium on Theory of Computing

Start page

331

End page

342

Subjects

Computer Science, Theory & Methods

•

Mathematics, Applied

•

Computer Science

•

Mathematics

•

integrality gap

•

discrepancy

•

linear program

•

discrepancy

•

algorithms

•

vectors

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

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

Rome, ITALY

Jun 20-24, 2022

Available on Infoscience
October 10, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/191363
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