{"corpus_id":23290566,"paper_sha":"1b20dccb5570d023e0679c52099d62eaf015437b","doi":"10.1007/s00453-018-00537-6","arxiv_id":"1704.07497","pmid":null,"pmcid":null,"mag_id":2964179137,"dblp_id":"journals/corr/WangZ17f","acl_id":null,"title":"Covering Uncertain Points in a Tree","year":2017,"publication_date":"2017-04-24","venue":"Algorithmica","journal":{"name":"Algorithmica","pages":"2346 - 2376","volume":"81"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":45,"citation_count":8,"influential_citation_count":1,"is_open_access":false,"arxiv_categories":["cs.CG","cs.DS"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"In this paper, we consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set P\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$${\\mathcal {P}}$$\\end{document} of n (weighted) demand points, and the location of each demand point Pi∈P\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$P_i\\in {{\\mathcal {P}}}$$\\end{document} is uncertain but is known to appear in one of mi\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$m_i$$\\end{document} points on T each associated with a probability. Given a covering rangeλ\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$\\lambda $$\\end{document}, the problem is to find a minimum number of points (called centers) on T to build facilities for serving (or covering) these demand points in the sense that for each uncertain point Pi∈P\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$P_i\\in {{\\mathcal {P}}}$$\\end{document}, the expected distance from Pi\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$P_i$$\\end{document} to at least one center is no more than λ\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$\\lambda $$\\end{document}. The problem has not been studied before. We present an O(|T|+Mlog2M)\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$O(|T|+M\\log ^2 M)$$\\end{document} time algorithm for the problem, where |T| is the number of vertices of T and M is the total number of locations of all uncertain points of P\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$${{\\mathcal {P}}}$$\\end{document}, i.e., M=∑Pi∈Pmi\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$$M=\\sum _{P_i\\in {{\\mathcal {P}}}}m_i$$\\end{document}. In addition, by using this algorithm, we solve a k-center problem on T for the uncertain points of P\\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$${{\\mathcal {P}}}$$\\end{document}.","claims":[{"public_id":"cl_d77321a78f63cd811d8005fa3fb523d4","status":"active","text":"An O(|T|+M log² M) time algorithm is presented for the problem, where |T| is the number of vertices of T and M is the total number of locations of all uncertain points.","confidence":0.95,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_d77321a78f63cd811d8005fa3fb523d4"},{"public_id":"cl_72ba5f8d73cfac38d0c029b5880fbc03","status":"active","text":"The problem is to find a minimum number of centers on a tree T to cover uncertain demand points such that for each uncertain point, the expected distance to at least one center is no more than λ.","confidence":0.95,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_72ba5f8d73cfac38d0c029b5880fbc03"},{"public_id":"cl_4d5f26871ebbf876b1a369338a025d74","status":"active","text":"Using the algorithm, a k-center problem on T for the uncertain points is solved.","confidence":0.9,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_4d5f26871ebbf876b1a369338a025d74"}],"concepts":[{"public_id":"co_2e060818f52765c3a18c127544cb0851","status":"active","name":"covering range λ","description":"The threshold λ that bounds the expected distance from an uncertain point to at least one center.","types":["parameter"],"aliases":["λ"],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_2e060818f52765c3a18c127544cb0851"},{"public_id":"co_3ed43522058ed5c71a6b3bf1ff783f12","status":"active","name":"k-center problem on T","description":"A variant of the k-center problem on a tree solved using the coverage algorithm for uncertain points.","types":["problem"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_3ed43522058ed5c71a6b3bf1ff783f12"},{"public_id":"co_450ec0eb329c95190f06dafd7b2dd79f","status":"active","name":"coverage problem for uncertain points in a tree","description":"A problem that seeks a minimum number of centers on a tree to cover uncertain demand points under an expected distance constraint.","types":["problem"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_450ec0eb329c95190f06dafd7b2dd79f"},{"public_id":"co_b7ba5f3a17c2ec87287c0996edab759d","status":"active","name":"O(|T|+M log² M) time algorithm","description":"The algorithm proposed for the coverage problem, with time complexity O(|T|+M log² M) where |T| is the number of tree vertices and M is the total number of locations of all uncertain points.","types":["algorithm"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b7ba5f3a17c2ec87287c0996edab759d"},{"public_id":"co_c622a246b3fca0d3e856d4f3496515be","status":"active","name":"expected distance","description":"The probabilistic distance measure used to evaluate coverage: for each uncertain point, the expected distance to at least one center must be no more than λ.","types":["measure"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c622a246b3fca0d3e856d4f3496515be"},{"public_id":"co_c9c02509448ac6bccc71d0e7892c8a48","status":"active","name":"uncertain demand points","description":"Points P_i in a tree whose exact location is uncertain but known to appear among m_i possible points each with an associated probability.","types":["entity"],"aliases":["uncertain points"],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c9c02509448ac6bccc71d0e7892c8a48"},{"public_id":"co_ca0e9477f897a690be478780d51738d6","status":"active","name":"tree T","description":"The tree structure containing the set of uncertain demand points and where centers are placed.","types":["structure"],"aliases":["T"],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ca0e9477f897a690be478780d51738d6"},{"public_id":"co_fe50cf1750faca332cc0dac9289b7cff","status":"active","name":"total number of locations M","description":"The sum over all uncertain points of the number of possible locations each point may appear, i.e., M = Σ_{P_i∈P} m_i.","types":["quantity"],"aliases":["M"],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["review"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_fe50cf1750faca332cc0dac9289b7cff"}],"external_ids":{"DOI":"10.1007/s00453-018-00537-6","ArXiv":"1704.07497","PubMed":null,"PubMedCentral":null,"MAG":2964179137,"DBLP":"journals/corr/WangZ17f","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://arxiv.org/pdf/1704.07497","landing_url":"https://arxiv.org/abs/1704.07497","source":"arxiv","pdf_url_source":"derived_arxiv","license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":636922,"paper_uid":"7a2805c8-e309-4cbd-901b-3c61c0ea172e","canonical_identity":{"paper_id":636922,"paper_uid":"7a2805c8-e309-4cbd-901b-3c61c0ea172e","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/23290566"}