Competitive Algorithms from Competitive Equilibria
From MaRDI portal
Publication:3177891
DOI10.1145/3136754zbMath1426.68309arXiv1404.1097MaRDI QIDQ3177891
Sungjin Im, Kamesh Munagala, Janardhan Kulkarni
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.1097
market equilibrium; total flow time; online scheduling; total completion time; non-clairvoyant; proportional fairness; polytope constraints; adversarial input
91B52: Special types of economic equilibria
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
68W27: Online algorithms; streaming algorithms
Related Items
Ascending-Price Algorithms for Unknown Markets, An Optimal Control Framework for Online Job Scheduling with General Cost Functions, Non-Clairvoyant Precedence Constrained Scheduling., Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling, An improved greedy algorithm for stochastic online scheduling on unrelated machines