[{"dc":{"title":["Online Connected Dominating Set Leasing"],"rights":["info:eu-repo/semantics/closedAccess"],"identifier":["https://ris.uni-paderborn.de/record/19978"],"source":["Markarian C. Online Connected Dominating Set Leasing. arXiv:180502994. 2018."],"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"],"creator":["Markarian, Christine"],"type":["info:eu-repo/semantics/preprint","doc-type:preprint","text"],"language":["eng"]},"date_updated":"2020-10-12T12:44:32Z","uri_base":"https://ris.uni-paderborn.de","publication":"arXiv:1805.02994","language":[{}],"author":[{"last_name":"Markarian","first_name":"Christine"}],"_id":"19978","message":"#hni-id 9743","abstract":[{"lang":"eng"}],"date_created":"2020-10-12T12:42:54Z","creator":{"login":"koala","id":"15415"},"dini_type":"doc-type:preprint","status":"public","_version":3,"type":"preprint","department":[{"_id":"63","tree":[{"_id":"7"},{"_id":"34"},{"_id":"44"},{"_id":"43"}]}],"citation":{"mla":"Markarian, Christine. “Online Connected Dominating Set Leasing.” ArXiv:1805.02994, 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} }","ieee":"C. Markarian, “Online Connected Dominating Set Leasing,” arXiv:1805.02994. 2018.","chicago":"Markarian, Christine. “Online Connected Dominating Set Leasing.” ArXiv:1805.02994, 2018.","short":"C. Markarian, ArXiv:1805.02994 (2018)."},"user_id":"15415"}]