Online Connected Dominating Set Leasing

C. Markarian, ArXiv:1805.02994 (2018).

No fulltext has been uploaded.
Preprint | English
We introduce the \emph{Online Connected Dominating Set Leasing} problem (OCDSL) in which we are given an undirected connected graph $G = (V, E)$, a set $\mathcal{L}$ of lease types each characterized by a duration and cost, and a sequence of subsets of $V$ arriving over time. A node can be leased using lease type $l$ for cost $c_l$ and remains active for time $d_l$. The adversary gives in each step $t$ a subset of nodes that need to be dominated by a connected subgraph consisting of nodes active at time $t$. The goal is to minimize the total leasing costs. OCDSL contains the \emph{Parking Permit Problem}~\cite{PPP} as a special subcase and generalizes the classical offline \emph{Connected Dominating Set} problem~\cite{Guha1998}. It has an $\Omega(\log ^2 n + \log |\mathcal{L}|)$ randomized lower bound resulting from lower bounds for the \emph{Parking Permit Problem} and the \emph{Online Set Cover} problem~\cite{Alon:2003:OSC:780542.780558,Korman}, where $|\mathcal{L}|$ is the number of available lease types and $n$ is the number of nodes in the input graph. We give a randomized $\mathcal{O}(\log ^2 n + \log |\mathcal{L}| \log n)$-competitive algorithm for OCDSL. We also give a deterministic algorithm for a variant of OCDSL in which the dominating subgraph need not be connected, the \emph{Online Dominating Set Leasing} problem. The latter is based on a simple primal-dual approach and has an $\mathcal{O}(|\mathcal{L}| \cdot \Delta)$-competitive ratio, where $\Delta$ is the maximum degree of the input graph.
Publishing Year
Journal Title

Cite this

Markarian C. Online Connected Dominating Set Leasing. arXiv:180502994. 2018.
Markarian, C. (2018). Online Connected Dominating Set Leasing. ArXiv:1805.02994.
@article{Markarian_2018, title={Online Connected Dominating Set Leasing}, journal={arXiv:1805.02994}, author={Markarian, Christine}, year={2018} }
Markarian, Christine. “Online Connected Dominating Set Leasing.” ArXiv:1805.02994, 2018.
C. Markarian, “Online Connected Dominating Set Leasing,” arXiv:1805.02994. 2018.
Markarian, Christine. “Online Connected Dominating Set Leasing.” ArXiv:1805.02994, 2018.


Marked Publications

Open Data LibreCat

Search this title in

Google Scholar