arXiv preprint ·

An Optimal Online Algorithm for Single-machine Scheduling with Two Agents

Peihai Liu, Kejun Zhao and Xiwen Lu

Published
Source
arXiv preprint, posted before peer review
Original
Read it at arXiv
Topics
Data Structures & AlgorithmsDiscrete Mathematics

Abstract

This paper addresses the online two-agent scheduling problem on a single machine, where jobs arrive over time. The objective is to minimize the weighted sum of the agents' makespans, denoted as $C_{\max}^A + θC_{\max}^B$, for a given priority weight $θ\ge 1$. A significant gap has persisted between the established theoretical lower bound on the competitive ratio and the performance of the best-known online algorithms. For the parameter range $1 \leq θ\leq \tfrac{1+\sqrt{5}}{2}$, we propose novel online algorithm which achieves a competitive ratio of $1+\tfracθ{1+θ}$. This result matches the theoretical lower bound.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Data Structures & Algorithms

Get the few papers worth your time in Data Structures & Algorithms every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics