[{"uri_base":"https://ris.uni-paderborn.de","language":[{}],"date_created":"2020-10-12T12:42:54Z","status":"public","author":[{"last_name":"Markarian","first_name":"Christine"}],"_id":"19978","type":"preprint","publication":"arXiv:1805.02994","department":[{"_id":"63","tree":[{"_id":"7"},{"_id":"34"},{"_id":"44"},{"_id":"43"}]}],"abstract":[{"lang":"eng"}],"date_updated":"2022-01-06T06:54:17Z","dc":{"creator":["Markarian, Christine"],"type":["info:eu-repo/semantics/preprint","doc-type:preprint","text","http://purl.org/coar/resource_type/c_816b"],"rights":["info:eu-repo/semantics/closedAccess"],"title":["Online Connected Dominating Set Leasing"],"description":["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."],"date":["2018"],"identifier":["https://ris.uni-paderborn.de/record/19978"],"source":["Markarian C. Online Connected Dominating Set Leasing. *arXiv:180502994*. 2018."],"language":["eng"]},"dini_type":"doc-type:preprint","creator":{"id":"15415","login":"koala"},"citation":{"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).","bibtex":"@article{Markarian_2018, title={Online Connected Dominating Set Leasing}, journal={arXiv:1805.02994}, author={Markarian, Christine}, year={2018} }","apa":"Markarian, C. (2018). Online Connected Dominating Set Leasing. *ArXiv:1805.02994*.","chicago":"Markarian, Christine. “Online Connected Dominating Set Leasing.” *ArXiv:1805.02994*, 2018."},"message":"#hni-id 9743","user_id":"15415"}]