Competitive Algorithms from Competitive Equilibria

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

zbMATH Keywords

market equilibrium; total flow time; online scheduling; total completion time; non-clairvoyant; proportional fairness; polytope constraints; adversarial input

Mathematics Subject Classification ID

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