Competitive Algorithms from Competitive Equilibria

DOI10.1145/3136754zbMath1426.68309arXiv1404.1097OpenAlexW2772039599MaRDI 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 equilibriumtotal flow timeonline schedulingtotal completion timenon-clairvoyantproportional fairnesspolytope constraintsadversarial input

Mathematics Subject Classification ID

Special types of economic equilibria (91B52) 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 ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ Ascending-Price Algorithms for Unknown Markets ⋮ Non-Clairvoyant Precedence Constrained Scheduling.

This page was built for publication: Competitive Algorithms from Competitive Equilibria