We consider the problem of partitioning n integers into two subsets of given cardinalities such that the discrepancy, the absolute value of the di\u000bfference of their sums, is minimized. The integers are i.i.d. random variables chosen uniformly from the set f1; … ;Mg. We study how the typical behavior of the optimal partition depends on n;M and the bias s, the diff\u000berence between the cardinalities of the two subsets in the partition. In particular, we rigorously establish this typical behavior as a function of the two parameters \u0014 := n????1 log2M and b := jsj=n by proving the existence of three distinct \\phases” in the \u0014bplane, characterized by the value of the discrepancy and the number of optimal solutions: a \\perfect phase” with exponentially many optimal solutions with discrepancy 0 or 1; a \\hard phase” with minimal discrepancy of order Me????\u0002(n); and a \\sorted phase” with an unique optimal partition of order Mn, obtained by putting the (s + n)=2 smallest integers in one subset. Our phase diagram covers all but a relatively small region in the \u0014b-plane. We also show that the three phases can be alternatively characterized by the number of basis solutions of the associated linear programming problem, and by the fraction of these basis solutions whose \u00061-valued components form optimal integer partitions of the subproblemwith the corresponding\u00a0 weights. We show in particular that this fraction is one in the sorted phase, and exponentially small in both the perfect and hard phases, and strictly exponentially smaller in the hard phase than in the perfect phase. Open\u00a0 problems are discussed, and numerical experiments are presented.<\/p>\n","protected":false},"excerpt":{"rendered":"
We consider the problem of partitioning n integers into two subsets of given cardinalities such that the discrepancy, the absolute value of the di\u000bfference of their sums, is minimized. The integers are i.i.d. random variables chosen uniformly from the set f1; … ;Mg. We study how the typical behavior of the optimal partition depends on […]<\/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":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13561],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-317837","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-locale-en_us"],"msr_publishername":"","msr_edition":"Random Structures and Algorithms 24","msr_affiliation":"","msr_published_date":"2003-12-05","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":1,"msr_main_download":"459576","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"phase-diagram-for-the-constrained-integer-partitioning-problem","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2016\/11\/Phase-Diagram-for-the-Constrained-Integer-Partitioning-Problem.pdf","id":459576,"label_id":0}],"msr_related_uploader":"","msr_attachments":[],"msr-author-ordering":[{"type":"user_nicename","value":"borgs","user_id":31278,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=borgs"},{"type":"user_nicename","value":"jchayes","user_id":32200,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=jchayes"},{"type":"text","value":"S. Mertens","user_id":0,"rest_url":false},{"type":"text","value":"B. Pittel","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/317837"}],"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":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/317837\/revisions"}],"predecessor-version":[{"id":523937,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/317837\/revisions\/523937"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=317837"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=317837"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=317837"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=317837"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=317837"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=317837"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=317837"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=317837"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=317837"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=317837"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=317837"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=317837"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=317837"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=317837"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=317837"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=317837"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}