Production systems use heuristics because they are faster or scale better than the corresponding optimal algorithms. Yet, practitioners are often unaware of how worse off a heuristic\u2019s solution may be with respect to the optimum in realistic scenarios. Leveraging two-stage games and convex optimization, we present a provable framework that unveils settings where a given heuristic underperforms.<\/p>\n","protected":false},"excerpt":{"rendered":"
Production systems use heuristics because they are faster or scale better than the corresponding optimal algorithms. Yet, practitioners are often unaware of how worse off a heuristic\u2019s solution may be with respect to the optimum in realistic scenarios. Leveraging two-stage games and convex optimization, we present a provable framework that unveils settings where a given […]<\/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":"guest","value":"pooria-namyar","user_id":"866415"},{"type":"user_nicename","value":"Behnaz Arzani","user_id":"37320"},{"type":"user_nicename","value":"Ryan Beckett","user_id":"37775"},{"type":"text","value":"Santiago Segarra","user_id":0},{"type":"user_nicename","value":"Srikanth Kandula","user_id":"33707"}],"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":"acm","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"Hot Topics in Networking","msr_doi":"","msr_arxiv_id":"","msr_mag_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_release_tracker_id":"","msr_highlight_type":"","msr_date_display_format":"","msr_main_download_label":"","msr_external_link_label":"","msr_doi_label":"","msr_published_date":"2022-11-14","msr_startdate":"","msr_presentation_date":"","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_year":2022,"msr_month":11,"msr_day":14,"msr_microsoftintellectualproperty":true,"msr_pub_id":"","msr_publication_uploader":[{"type":"file","viewUrl":"https:\/\/research.codeghost.online\/en-us\/research\/wp-content\/uploads\/2022\/11\/hotnets22-final125.pdf","id":897084,"title":"hotnets22-final125","label_id":243109,"label":0}],"msr_related_uploader":[],"msr_original_fields_of_study":[],"msr_s2_paper_id":"","msr_s2_pdf_url":"","msr_citation_count_updated":"","msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":null,"footnotes":""},"msr-research-highlight":[],"research-area":[13547],"msr-publication-type":[193716],"msr-publisher":[],"msr-publication-cta":[],"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-897075","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-systems-and-networking","msr-locale-en_us"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2022-11-14","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":"acm","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":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","viewUrl":"https:\/\/research.codeghost.online\/en-us\/research\/wp-content\/uploads\/2022\/11\/hotnets22-final125.pdf","id":"897084","title":"hotnets22-final125","label_id":"243109","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":[{"id":897084,"url":"https:\/\/research.codeghost.online\/en-us\/research\/wp-content\/uploads\/2022\/11\/hotnets22-final125.pdf"}],"msr-author-ordering":[{"type":"guest","value":"pooria-namyar","user_id":866415,"rest_url":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=pooria-namyar"},{"type":"user_nicename","value":"Behnaz Arzani","user_id":37320,"rest_url":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Behnaz Arzani"},{"type":"user_nicename","value":"Ryan Beckett","user_id":37775,"rest_url":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Ryan Beckett"},{"type":"text","value":"Santiago Segarra","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Srikanth Kandula","user_id":33707,"rest_url":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Srikanth Kandula"}],"msr_impact_theme":[],"msr_research_lab":[199565],"msr_event":[],"msr_group":[144899],"msr_project":[982158,716230],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":982158,"post_title":"MetaOpt: A Comprehensive Heuristic Analysis and Optimization Tool","post_name":"finding-adversarial-inputs-for-heuristics","post_type":"msr-project","post_date":"2023-11-08 12:39:02","post_modified":"2026-08-07 02:14:39","post_status":"publish","permalink":"https:\/\/research.codeghost.online\/en-us\/research\/project\/finding-adversarial-inputs-for-heuristics\/","post_excerpt":"Towards efficient heuristic design where we achieve quantifiable and confident performance We use heuristics all the time across many systems, including those that are critical to production services. Production systems use heuristics because they are faster or scale better than their optimal counterparts. But practitioners often don\u2019t know the performance gap between the heuristic and the optimal, or another heuristic in realistic scenarios. In many cases, theoreticians also have been unable to prove tight bounds…","_links":{"self":[{"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/982158"}]}},{"ID":716230,"post_title":"PathBlazer: 5G transport orchestration on the Azure WAN","post_name":"pathblazer-5g-transport-orchestration-on-the-azure-wan","post_type":"msr-project","post_date":"2021-01-08 13:19:30","post_modified":"2024-10-02 16:25:18","post_status":"publish","permalink":"https:\/\/research.codeghost.online\/en-us\/research\/project\/pathblazer-5g-transport-orchestration-on-the-azure-wan\/","post_excerpt":"We are building networking & distributed systems technology to support 5G traffic on the Azure global Wide Area Network.","_links":{"self":[{"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/716230"}]}}]},"_links":{"self":[{"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/897075","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/897075\/revisions"}],"predecessor-version":[{"id":1091241,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/897075\/revisions\/1091241"}],"wp:attachment":[{"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/media?parent=897075"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=897075"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=897075"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=897075"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=897075"},{"taxonomy":"msr-publication-cta","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-cta?post=897075"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=897075"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=897075"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=897075"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=897075"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=897075"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=897075"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=897075"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/research.codeghost.online\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=897075"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}