---
_id: '379'
abstract:
- lang: eng
  text: In the leasing variant of Set Cover presented by Anthony et al.[1], elements
    U arrive over time and must be covered by sets from a familyF of subsets of U.
    Each set can be leased for K different periods of time.Let |U| = n and |F| = m.
    Leasing a set S for a period k incurs a cost ckS and allows S to cover its elements
    for the next lk time steps. The objectiveis to minimize the total cost of the
    sets leased, such that elements arrivingat any time t are covered by sets which
    contain them and are leased duringtime t. Anthony et al. [1] gave an optimal O(log
    n)-approximation forthe problem in the offline setting, unless P = NP [22]. In
    this paper, wegive randomized algorithms for variants of Set Cover Leasing in
    the onlinesetting, including a generalization of Online Set Cover with Repetitionspresented
    by Alon et al. [2], where elements appear multiple times andmust be covered by
    a different set at each arrival. Our results improve theO(log2(mn)) competitive
    factor of Online Set Cover with Repetitions [2]to O(log d log(dn)) = O(logmlog(mn)),
    where d is the maximum numberof sets an element belongs to.
author:
- first_name: Sebastian
  full_name: Abshoff, Sebastian
  last_name: Abshoff
- first_name: Christine
  full_name: Markarian, Christine
  id: '37612'
  last_name: Markarian
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Abshoff S, Markarian C, Meyer auf der Heide F. Randomized Online Algorithms
    for Set Cover Leasing Problems. In: <i>Proceedings of the 8th Annual International
    Conference on Combinatorial Optimization and Applications (COCOA)</i>. LNCS. ;
    2014:25-34. doi:<a href="https://doi.org/10.1007/978-3-319-12691-3_3">10.1007/978-3-319-12691-3_3</a>'
  apa: Abshoff, S., Markarian, C., &#38; Meyer auf der Heide, F. (2014). Randomized
    Online Algorithms for Set Cover Leasing Problems. In <i>Proceedings of the 8th
    Annual International Conference on Combinatorial Optimization and Applications
    (COCOA)</i> (pp. 25–34). <a href="https://doi.org/10.1007/978-3-319-12691-3_3">https://doi.org/10.1007/978-3-319-12691-3_3</a>
  bibtex: '@inproceedings{Abshoff_Markarian_Meyer auf der Heide_2014, series={LNCS},
    title={Randomized Online Algorithms for Set Cover Leasing Problems}, DOI={<a href="https://doi.org/10.1007/978-3-319-12691-3_3">10.1007/978-3-319-12691-3_3</a>},
    booktitle={Proceedings of the 8th Annual International Conference on Combinatorial
    Optimization and Applications (COCOA)}, author={Abshoff, Sebastian and Markarian,
    Christine and Meyer auf der Heide, Friedhelm}, year={2014}, pages={25–34}, collection={LNCS}
    }'
  chicago: Abshoff, Sebastian, Christine Markarian, and Friedhelm Meyer auf der Heide.
    “Randomized Online Algorithms for Set Cover Leasing Problems.” In <i>Proceedings
    of the 8th Annual International Conference on Combinatorial Optimization and Applications
    (COCOA)</i>, 25–34. LNCS, 2014. <a href="https://doi.org/10.1007/978-3-319-12691-3_3">https://doi.org/10.1007/978-3-319-12691-3_3</a>.
  ieee: S. Abshoff, C. Markarian, and F. Meyer auf der Heide, “Randomized Online Algorithms
    for Set Cover Leasing Problems,” in <i>Proceedings of the 8th Annual International
    Conference on Combinatorial Optimization and Applications (COCOA)</i>, 2014, pp.
    25–34.
  mla: Abshoff, Sebastian, et al. “Randomized Online Algorithms for Set Cover Leasing
    Problems.” <i>Proceedings of the 8th Annual International Conference on Combinatorial
    Optimization and Applications (COCOA)</i>, 2014, pp. 25–34, doi:<a href="https://doi.org/10.1007/978-3-319-12691-3_3">10.1007/978-3-319-12691-3_3</a>.
  short: 'S. Abshoff, C. Markarian, F. Meyer auf der Heide, in: Proceedings of the
    8th Annual International Conference on Combinatorial Optimization and Applications
    (COCOA), 2014, pp. 25–34.'
date_created: 2017-10-17T12:42:06Z
date_updated: 2022-01-06T06:59:36Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-12691-3_3
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-20T07:12:57Z
  date_updated: 2018-03-20T07:12:57Z
  file_id: '1395'
  file_name: 379-COCOA14.pdf
  file_size: 214299
  relation: main_file
  success: 1
file_date_updated: 2018-03-20T07:12:57Z
has_accepted_license: '1'
page: 25-34
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 8th Annual International Conference on Combinatorial
  Optimization and Applications (COCOA)
series_title: LNCS
status: public
title: Randomized Online Algorithms for Set Cover Leasing Problems
type: conference
user_id: '15504'
year: '2014'
...