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

^*此作品的通讯作者

Hong Kong Polytechnic University
Beijing Normal University
United International College (UIC)
City University of Hong Kong

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

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.

源语言	英语
页（从-至）	72-75
页数	4
期刊	Operations Research Letters
卷	50
期	1
DOI	https://doi.org/10.1016/j.orl.2021.12.007
出版状态	已出版 - 1月 2022
已对外发布	是

访问文件

10.1016/j.orl.2021.12.007

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{6c0f135bc848479b95b21ebdf6d00437,

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 = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2022",

month = jan,

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

language = "英语",

volume = "50",

pages = "72--75",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A note on the online interval scheduling secretary problem

AU - Li, Bo

AU - Wang, Chenhao

AU - Zhang, Ruilong

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 - https://www.scopus.com/pages/publications/85122065966

U2 - 10.1016/j.orl.2021.12.007

DO - 10.1016/j.orl.2021.12.007

M3 - 文章

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

摘要

访问文件

其它文件与链接

指纹

引用此