A note on the online interval scheduling secretary problem

Bo Li; Chenhao Wang; Ruilong Zhang

doi:10.1016/j.orl.2021.12.007

A note on the online interval scheduling secretary problem

Bo Li, Chenhao Wang, Ruilong Zhang

Research output: Journal article publication › Journal article › Academic research › peer-review

Abstract

The interval scheduling secretary problem models the scenario when a number of job intervals arrive randomly and the decider needs to assign some of them to machines irrevocably such that all assigned job intervals can be processed by machines without overlap, with the goal of maximizing the social welfare. Im and Wang ((2011) [7]) designed an almost optimal logarithm-competitive online algorithm for the single-machine case. In this note, we extend this result to multiple heterogeneous machines. Our algorithm preserves the competitive ratio and is thus nearly optimal.

Original language	English
Pages (from-to)	72-75
Number of pages	4
Journal	Operations Research Letters
Volume	50
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2021.12.007
Publication status	Published - Jan 2022

Keywords

Interval scheduling
Online algorithms
Secretary problem

ASJC Scopus subject areas

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

More information

10.1016/j.orl.2021.12.007

Cite this

@article{02aa1996bb5a4573bde17925166f0d93,

title = "A note on the online interval scheduling secretary problem",

abstract = "The interval scheduling secretary problem models the scenario when a number of job intervals arrive randomly and the decider needs to assign some of them to machines irrevocably such that all assigned job intervals can be processed by machines without overlap, with the goal of maximizing the social welfare. Im and Wang ((2011) [7]) designed an almost optimal logarithm-competitive online algorithm for the single-machine case. In this note, we extend this result to multiple heterogeneous machines. Our algorithm preserves the competitive ratio and is thus nearly optimal.",

keywords = "Interval scheduling, Online algorithms, Secretary problem",

author = "Bo Li and Chenhao Wang and Ruilong Zhang",

note = "Funding Information: This work is partially funded by the Research Grants Council of HKSAR under Grant No. PolyU 25211321 , NSFC under Grant No. 62102333 , and The Hong Kong Polytechnic University under Grant No. P0034420 . Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2022",

month = jan,

doi = "10.1016/j.orl.2021.12.007",

language = "English",

volume = "50",

pages = "72--75",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - A note on the online interval scheduling secretary problem

AU - Li, Bo

AU - Wang, Chenhao

AU - Zhang, Ruilong

N1 - Funding Information: This work is partially funded by the Research Grants Council of HKSAR under Grant No. PolyU 25211321 , NSFC under Grant No. 62102333 , and The Hong Kong Polytechnic University under Grant No. P0034420 . Publisher Copyright: © 2021 Elsevier B.V.

PY - 2022/1

Y1 - 2022/1

N2 - The interval scheduling secretary problem models the scenario when a number of job intervals arrive randomly and the decider needs to assign some of them to machines irrevocably such that all assigned job intervals can be processed by machines without overlap, with the goal of maximizing the social welfare. Im and Wang ((2011) [7]) designed an almost optimal logarithm-competitive online algorithm for the single-machine case. In this note, we extend this result to multiple heterogeneous machines. Our algorithm preserves the competitive ratio and is thus nearly optimal.

AB - The interval scheduling secretary problem models the scenario when a number of job intervals arrive randomly and the decider needs to assign some of them to machines irrevocably such that all assigned job intervals can be processed by machines without overlap, with the goal of maximizing the social welfare. Im and Wang ((2011) [7]) designed an almost optimal logarithm-competitive online algorithm for the single-machine case. In this note, we extend this result to multiple heterogeneous machines. Our algorithm preserves the competitive ratio and is thus nearly optimal.

KW - Interval scheduling

KW - Online algorithms

KW - Secretary problem

UR - http://www.scopus.com/inward/record.url?scp=85122065966&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2021.12.007

DO - 10.1016/j.orl.2021.12.007

M3 - Journal article

AN - SCOPUS:85122065966

SN - 0167-6377

VL - 50

SP - 72

EP - 75

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

A note on the online interval scheduling secretary problem

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this