{"id":1103886,"date":"2024-11-14T09:56:15","date_gmt":"2024-11-14T17:56:15","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&#038;p=1103886"},"modified":"2024-11-15T10:04:59","modified_gmt":"2024-11-15T18:04:59","slug":"stochastic-%e2%84%93p-load-balancing-and-moment-problems-via-the-l-function-method","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/stochastic-%e2%84%93p-load-balancing-and-moment-problems-via-the-l-function-method\/","title":{"rendered":"Stochastic \u2113p Load Balancing and Moment Problems via the L-Function Method"},"content":{"rendered":"<p>This paper considers stochastic optimization problems whose objective functions involve powers of random variables. For a concrete example, consider the classic Stochastic\u00a0<i>\u2113<sub>p<\/sub><\/i>\u00a0Load\u00a0Balancing\u00a0Problem (StochLoadBal<sub><i>p<\/i><\/sub>): There are\u00a0<i>m<\/i>\u00a0machines and\u00a0<i>n<\/i>\u00a0jobs, and we are given independent random variables\u00a0<i>Y<sub>ij<\/sub><\/i>\u00a0describing the distribution of the load incurred on machine\u00a0<i>i<\/i>\u00a0if we assign job\u00a0<i>j<\/i>\u00a0to it. The goal is to assign each job to the machines in order to minimize the expected\u00a0<i>\u2113<sub>p<\/sub><\/i>-norm of the total load incurred over the machines. That is, letting\u00a0<i>J<sub>i<\/sub><\/i>\u00a0denote the jobs assigned to machine\u00a0<i>i<\/i>, we want to minimize \\(\\mathbb{E}(\\sum_i(\\sum_{j{\\epsilon}J_i}Y_{ij})^p)^{1\/p}\\). While convex relaxations represent one of the most powerful algorithmic tools, in problems such as StochLoadBal<sub><i>p<\/i><\/sub>\u00a0the main difficulty is to capture such objective function in a way that only depends on each random variable separately.<\/p>\n<p>In this paper, show how to capture\u00a0<i>p<\/i>-power-type objectives in such separable way by using the\u00a0<i>L-function<\/i>\u00a0method. This method was precisely introduced by Latala to capture in a sharp way the moment of sums of random variables through the individual marginals. We first show how this quickly leads to a constant-factor approximation for very general subset selection problem with\u00a0<i>p<\/i>-moment objective.<\/p>\n<p><span style=\"font-size: 1rem;\">Moreover, we give a constant-factor approximation for StochLoadBal<\/span><sub><i>p<\/i><\/sub><span style=\"font-size: 1rem;\">, improving on the recent <\/span><i style=\"font-size: 1rem;\">O<\/i><span style=\"font-size: 1rem;\">(<\/span><i style=\"font-size: 1rem;\">p\/<\/i><span style=\"font-size: 1rem;\">\u00a0ln\u00a0<\/span><i style=\"font-size: 1rem;\">p<\/i><span style=\"font-size: 1rem;\">)-approximation of [Gupta et al., SODA 18]. Here the application of the method is much more involved. In particular, we need to prove structural results connecting the expected <\/span><i style=\"font-size: 1rem;\">\u2113<sub>p<\/sub><\/i><span style=\"font-size: 1rem;\">-norm of a random vector with the\u00a0<\/span><i style=\"font-size: 1rem;\">p<\/i><span style=\"font-size: 1rem;\">-moments of its coordinate-marginals (machine loads) in a sharp way, taking into account simultaneously the different scales of the loads that are incurred in the different machines by an\u00a0<\/span><i style=\"font-size: 1rem;\">unknown<\/i><span style=\"font-size: 1rem;\">\u00a0assignment. Moreover, our starting convex (indeed linear) relaxation has exponentially many constraints that are not conducive to integral rounding; we need to use the solution of this LP to obtain a reduced LP which can then be used to obtain the desired assignment.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This paper considers stochastic optimization problems whose objective functions involve powers of random variables. For a concrete example, consider the classic Stochastic\u00a0\u2113p\u00a0Load\u00a0Balancing\u00a0Problem (StochLoadBalp): There are\u00a0m\u00a0machines and\u00a0n\u00a0jobs, and we are given independent random variables\u00a0Yij\u00a0describing the distribution of the load incurred on machine\u00a0i\u00a0if we assign job\u00a0j\u00a0to it. The goal is to assign each job to the machines [&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":[{"type":"user_nicename","value":"Marco Molinaro","user_id":"42204"}],"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"SODA","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":null,"msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2019-10-10","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":false,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":null,"footnotes":""},"msr-research-highlight":[],"research-area":[13561],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[246691,246907],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-1103886","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-locale-en_us","msr-field-of-study-computer-science","msr-field-of-study-mathematics"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2019-10-10","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","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":0,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"doi","viewUrl":"false","id":"false","title":"https:\/\/doi.org\/10.1137\/1.9781611975482.22","label_id":"243106","label":0},{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/arxiv.org\/abs\/1810.05245","label_id":"243109","label":0},{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611975482.22","label_id":"243132","label":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":"Marco Molinaro","user_id":42204,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Marco Molinaro"}],"msr_impact_theme":[],"msr_research_lab":[199565],"msr_event":[],"msr_group":[569136],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1103886","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":10,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1103886\/revisions"}],"predecessor-version":[{"id":1104588,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1103886\/revisions\/1104588"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=1103886"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=1103886"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=1103886"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=1103886"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=1103886"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=1103886"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=1103886"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=1103886"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=1103886"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=1103886"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=1103886"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=1103886"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=1103886"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}