{"id":324335,"date":"2016-11-18T15:39:27","date_gmt":"2016-11-18T23:39:27","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/?post_type=msr-research-item&#038;p=324335"},"modified":"2018-10-16T20:39:49","modified_gmt":"2018-10-17T03:39:49","slug":"facility-location-client-latencies-linear-programming-based-techniques-minimum-latency-problems","status":"publish","type":"msr-research-item","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/facility-location-client-latencies-linear-programming-based-techniques-minimum-latency-problems\/","title":{"rendered":"Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems"},"content":{"rendered":"<p>We introduce a problem that is a common generalization of the uncapacitated facility location and minimum latency (ML) problems, where facilities need to be opened to serve clients and also need to be sequentially activated before they can provide service. Formally, we are given a set <i>F<\/i> of <i>n<\/i> facilities with facility-opening costs <i>fi<\/i>, a set <i>D<\/i> of <i>m<\/i> clients, connection costs <i>cij<\/i> specifying the cost of assigning a client <i>j<\/i> to a facility <i>i<\/i>, a root node <i>r<\/i> denoting the depot, and a time metric d on <i>F<\/i>\u222a{<i>r<\/i>}. Our goal is to open a subset <i>F<\/i> of facilities, find a path <i>P<\/i> starting at <i>r<\/i> and spanning <i>F<\/i> to activate the open facilities, and connect each client <i>j<\/i> to a facility \u03c6(<i>j<\/i>) \u03b5 <i>F<\/i>, so as to minimize \u03a3<i>i<\/i>\u2208<i>F<\/i><sup><i>f<\/i><\/sup><i>i<\/i>+ \u03a3<i>j<\/i>\u2208<i>D<\/i><sup>(<i>C<\/i>\u03c6(<i>j<\/i>),<i>j<\/i><\/sup> +<i>tj<\/i>), where <i>tj<\/i> is the time taken to reach \u03c6(<i>j<\/i>) along path <i>P<\/i>. We call this the minimum latency uncapacitated facility location (MLUFL) problem.<\/p>\n<p>Our main result is an <i>O<\/i>(log <i>n<\/i> \u010b max(log <i>n<\/i>, log<i>m<\/i>))-approximation for MLUFL. We also show that any improvement in this approximation guarantee, implies an improvement in the (current-best) approximation factor for group Steiner tree. We obtain constant approximations for two natural special cases of the problem: (a) related MLUFL (metric connection costs that are a scalar multiple of the time metric); (b) metric uniform MLUFL (metric connection costs, uniform time-metric). Our LP-based methods are versatile and easily adapted to yield approximation guarantees for MLUFL in various more general settings, such as (i) when the latency-cost of a client is a function of the delay faced by the facility to which it is connected; and (ii) the <i>k<\/i>-route version, where k vehicles are routed in parallel to activate the open facilities. Our LP-based understanding of MLUFL also offers some LP-based insights into ML, which we believe is a promising direction for obtaining improvements for ML.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We introduce a problem that is a common generalization of the uncapacitated facility location and minimum latency (ML) problems, where facilities need to be opened to serve clients and also need to be sequentially activated before they can provide service. Formally, we are given a set F of n facilities with facility-opening costs fi, a [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"Springer-Verlag Berlin, Heidelberg","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"IPCO'11 Proceedings of the 15th international conference on Integer programming and combinatoral optimization, New York, NY","msr_editors":"","msr_how_published":"","msr_isbn":"978-3-642-20806-5","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"92-103","msr_page_range_start":"92","msr_page_range_end":"103","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"IPCO'11 Proceedings of the 15th international conference on Integer programming and combinatoral optimization, New York, NY","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2011-06-15","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561,13560],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-324335","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-research-area-programming-languages-software-engineering","msr-locale-en_us"],"msr_publishername":"Springer-Verlag Berlin, Heidelberg","msr_edition":"IPCO'11 Proceedings of the 15th international conference on Integer programming and combinatoral optimization, New York, NY","msr_affiliation":"","msr_published_date":"2011-06-15","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"92-103","msr_chapter":"","msr_isbn":"978-3-642-20806-5","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"324338","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems","viewUrl":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2016\/11\/Facility-Location-with-Client-Latencies-Linear-Programming-based-Techniques-for-Minimum-Latency-Problems.pdf","id":324338,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"user_nicename","value":"dechakr","user_id":31593,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=dechakr"},{"type":"text","value":"Chaitanya Swamy","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/324335","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/324335\/revisions"}],"predecessor-version":[{"id":529406,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/324335\/revisions\/529406"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=324335"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=324335"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=324335"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=324335"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=324335"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=324335"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=324335"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=324335"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=324335"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=324335"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=324335"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=324335"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=324335"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}