The Competitiveness of On-Line Assignments
From MaRDI portal
Publication:4327820
DOI10.1006/jagm.1995.1008zbMath0818.68026OpenAlexW2064467943MaRDI QIDQ4327820
Joseph (Seffi) Naor, Raphael Rom, Yossi Azar
Publication date: 1995
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1995.1008
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Vertex cover meets scheduling ⋮ The shortest first coordination mechanism for a scheduling game with parallel-batching machines ⋮ Parallel machine scheduling under a grade of service provision ⋮ On-line service scheduling ⋮ Online parallel machines scheduling with two hierarchies ⋮ Online scheduling on two uniform machines subject to eligibility constraints ⋮ Optimal Coordination Mechanisms for Unrelated Machine Scheduling ⋮ Efficient coordination mechanisms for unrelated machine scheduling ⋮ Worst-case Nash equilibria in restricted routing ⋮ Online and semi-online scheduling of two machines under a grade of service provision ⋮ On the optimality of the \(TLS\) algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines ⋮ iGreen: green scheduling for peak demand minimization ⋮ Rejecting jobs to minimize load and maximum flow-time ⋮ An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times ⋮ Coordination mechanisms for parallel machine scheduling ⋮ Fair online load balancing ⋮ Multiprofessor scheduling ⋮ Configuration balancing for stochastic requests ⋮ Online hierarchical scheduling: an approach using mathematical programming ⋮ Coordination mechanisms with hybrid local policies ⋮ Strategic Scheduling Games: Equilibria and Efficiency ⋮ Scheduling jobs with equal processing times subject to machine eligibility constraints ⋮ Non-clairvoyant scheduling games ⋮ Tight Bounds for Online Vector Scheduling ⋮ On-line load balancing made simple: greedy strikes back ⋮ Preemptive scheduling on a small number of hierarchical machines ⋮ On-line algorithms for the channel assignment problem in cellular networks. ⋮ The hierarchical model for load balancing on two machines ⋮ Scheduling unit length jobs on parallel machines with lookahead information ⋮ Robust algorithms for preemptive scheduling ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Performance of service policies in a specialized service system with parallel servers ⋮ Online scheduling on parallel machines with two goS levels ⋮ Distributed backup placement in networks ⋮ A coordination mechanism for a scheduling game with parallel-batching machines ⋮ Minimizing maximum (weighted) flow-time on related and unrelated machines ⋮ A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS ⋮ Deferred on-line bipartite matching ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Online scheduling of two job types on a set of multipurpose machines with unit processing times ⋮ An optimal online algorithm for fractional scheduling on uniform machines with three hierarchies ⋮ A note on ``An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs ⋮ Improved bounds for online scheduling with eligibility constraints ⋮ On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints ⋮ Price of anarchy in parallel processing ⋮ On-line load balancing of temporary tasks revisited ⋮ Optimal online algorithms for scheduling on two identical machines under a grade of service ⋮ Decentralized utilitarian mechanisms for scheduling games ⋮ Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs ⋮ Coordination mechanisms for selfish scheduling ⋮ On the \(k\)-orientability of random graphs ⋮ Online scheduling with unit processing times and processing set restrictions ⋮ Online fractional hierarchical scheduling on uniformly related machines ⋮ Online scheduling with migration on two hierarchical machines ⋮ New algorithms for related machines with temporary jobs. ⋮ Priority algorithms for makespan minimization in the subset model. ⋮ On-line scheduling with precedence constraints
