Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems

DOI10.1007/s00453-019-00583-8zbMath1429.68032arXiv1502.03946OpenAlexW2950293225WikidataQ127885944 ScholiaQ127885944MaRDI QIDQ2319627

Nguyen Kim Thang, Spyros Angelopoulos, Giorgio Lucarelli, Kim Thang Nguyen

Publication date: 20 August 2019

Published in: Algorithmica, Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.03946

zbMATH Keywords

schedulingonline algorithmsprimal-dualdual-fittinggeneralized flow-time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Related Items (5)

An Optimal Control Framework for Online Job Scheduling with General Cost Functions ⋮ Optimal Speed Scaling with a Solar Cell ⋮ A best possible online algorithm for minimizing the total completion time and the total soft penalty cost ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online weighted flow time and deadline scheduling
• Nonclairvoyant scheduling
• Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems
• Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling
• Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling
• Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions
• Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules
• Scalably scheduling processes with arbitrary speedup curves
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Scalably Scheduling Power-Heterogeneous Processors
• Speed is as powerful as clairvoyance
• Primal Dual Gives Almost Optimal Energy-Efficient Online Algorithms
• How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions
• Competitive algorithms from competitive equilibria
• Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms
• Online Scheduling with General Cost Functions
• LATIN 2004: Theoretical Informatics
• Scheduling in the dark

This page was built for publication: Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems