Online selection of intervals and t-intervals

Unnar Th Bachmann; Magnús M. Halldórsson; Hadas Shachnai

doi:10.1016/j.ic.2013.10.004

Online selection of intervals and t-intervals

Unnar Th Bachmann, Magnús M. Halldórsson, Hadas Shachnai^*

^*Corresponding author for this work

Department of Computer Science

Reykjavik University, Iceland

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

A t-interval is a union of at most t half-open intervals on the real line. An interval is the special case where t=1. In this paper we study the problems of online selection of intervals and t-intervals. We derive lower bounds and (almost) matching upper bounds on the competitive ratios of randomized algorithms for selecting intervals, 2-intervals and t-intervals, for any t>2. While offline t-interval selection has been studied before, the online version is considered here for the first time.

Original language	English
Pages (from-to)	1-11
Number of pages	11
Journal	Information and Computation
Volume	233
DOIs	https://doi.org/10.1016/j.ic.2013.10.004
Publication status	Published - 2013

Other keywords

Competitive analysis
Interval selection
Online algorithms

Access to Document

10.1016/j.ic.2013.10.004

Cite this

@article{732a9326d96747eea2abb739b396b5dc,

title = "Online selection of intervals and t-intervals",

abstract = "A t-interval is a union of at most t half-open intervals on the real line. An interval is the special case where t=1. In this paper we study the problems of online selection of intervals and t-intervals. We derive lower bounds and (almost) matching upper bounds on the competitive ratios of randomized algorithms for selecting intervals, 2-intervals and t-intervals, for any t>2. While offline t-interval selection has been studied before, the online version is considered here for the first time.",

keywords = "Competitive analysis, Interval selection, Online algorithms",

author = "Bachmann, {Unnar Th} and Halld{\'o}rsson, {Magn{\'u}s M.} and Hadas Shachnai",

year = "2013",

doi = "10.1016/j.ic.2013.10.004",

language = "English",

volume = "233",

pages = "1--11",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Online selection of intervals and t-intervals

AU - Bachmann, Unnar Th

AU - Halldórsson, Magnús M.

AU - Shachnai, Hadas

PY - 2013

Y1 - 2013

N2 - A t-interval is a union of at most t half-open intervals on the real line. An interval is the special case where t=1. In this paper we study the problems of online selection of intervals and t-intervals. We derive lower bounds and (almost) matching upper bounds on the competitive ratios of randomized algorithms for selecting intervals, 2-intervals and t-intervals, for any t>2. While offline t-interval selection has been studied before, the online version is considered here for the first time.

AB - A t-interval is a union of at most t half-open intervals on the real line. An interval is the special case where t=1. In this paper we study the problems of online selection of intervals and t-intervals. We derive lower bounds and (almost) matching upper bounds on the competitive ratios of randomized algorithms for selecting intervals, 2-intervals and t-intervals, for any t>2. While offline t-interval selection has been studied before, the online version is considered here for the first time.

KW - Competitive analysis

KW - Interval selection

KW - Online algorithms

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

U2 - 10.1016/j.ic.2013.10.004

DO - 10.1016/j.ic.2013.10.004

M3 - Article

AN - SCOPUS:84888149368

SN - 0890-5401

VL - 233

SP - 1

EP - 11

JO - Information and Computation

JF - Information and Computation

ER -

Online selection of intervals and t-intervals

Abstract

Other keywords

Access to Document

Fingerprint

Cite this