---
_id: '19978'
abstract:
- lang: eng
text: "We introduce the \\emph{Online Connected Dominating Set Leasing} problem\r\n(OCDSL)
in which we are given an undirected connected graph $G = (V, E)$, a set\r\n$\\mathcal{L}$
of lease types each characterized by a duration and cost, and a\r\nsequence of
subsets of $V$ arriving over time. A node can be leased using lease\r\ntype $l$
for cost $c_l$ and remains active for time $d_l$. The adversary gives\r\nin each
step $t$ a subset of nodes that need to be dominated by a connected\r\nsubgraph
consisting of nodes active at time $t$. The goal is to minimize the\r\ntotal leasing
costs. OCDSL contains the \\emph{Parking Permit\r\nProblem}~\\cite{PPP} as a special
subcase and generalizes the classical offline\r\n\\emph{Connected Dominating Set}
problem~\\cite{Guha1998}. It has an $\\Omega(\\log\r\n^2 n + \\log |\\mathcal{L}|)$
randomized lower bound resulting from lower bounds\r\nfor the \\emph{Parking Permit
Problem} and the \\emph{Online Set Cover}\r\nproblem~\\cite{Alon:2003:OSC:780542.780558,Korman},
where $|\\mathcal{L}|$ is the\r\nnumber of available lease types and $n$ is the
number of nodes in the input\r\ngraph. We give a randomized $\\mathcal{O}(\\log
^2 n + \\log |\\mathcal{L}| \\log\r\nn)$-competitive algorithm for OCDSL. We also
give a deterministic algorithm for\r\na variant of OCDSL in which the dominating
subgraph need not be connected, the\r\n\\emph{Online Dominating Set Leasing} problem.
The latter is based on a simple\r\nprimal-dual approach and has an $\\mathcal{O}(|\\mathcal{L}|
\\cdot\r\n\\Delta)$-competitive ratio, where $\\Delta$ is the maximum degree of
the input\r\ngraph."
author:
- first_name: Christine
full_name: Markarian, Christine
last_name: Markarian
citation:
ama: Markarian C. Online Connected Dominating Set Leasing. *arXiv:180502994*.
2018.
apa: Markarian, C. (2018). Online Connected Dominating Set Leasing. *ArXiv:1805.02994*.
bibtex: '@article{Markarian_2018, title={Online Connected Dominating Set Leasing},
journal={arXiv:1805.02994}, author={Markarian, Christine}, year={2018} }'
chicago: Markarian, Christine. “Online Connected Dominating Set Leasing.” *ArXiv:1805.02994*,
2018.
ieee: C. Markarian, “Online Connected Dominating Set Leasing,” *arXiv:1805.02994*.
2018.
mla: Markarian, Christine. “Online Connected Dominating Set Leasing.” *ArXiv:1805.02994*,
2018.
short: C. Markarian, ArXiv:1805.02994 (2018).
date_created: 2020-10-12T12:42:54Z
date_updated: 2022-01-06T06:54:17Z
department:
- _id: '63'
language:
- iso: eng
publication: arXiv:1805.02994
status: public
title: Online Connected Dominating Set Leasing
type: preprint
user_id: '15415'
year: '2018'
...