{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:15:38Z","timestamp":1781345738080,"version":"3.54.1"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,12,11]],"date-time":"2017-12-11T00:00:00Z","timestamp":1512950400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundatio","doi-asserted-by":"publisher","award":["CCF-1008065, CCF-1409130, CCF-1617653"],"award-info":[{"award-number":["CCF-1008065, CCF-1409130, CCF-1617653"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-14-1-0366"],"award-info":[{"award-number":["W911NF-14-1-0366"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Cisco","award":["Gift from Cisco"],"award-info":[{"award-number":["Gift from Cisco"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0745761, CCF-1008065, CCF-1348696, CCF-1408784, IIS-0964560, IIS-1447554"],"award-info":[{"award-number":["CCF-0745761, CCF-1008065, CCF-1348696, CCF-1408784, IIS-0964560, IIS-1447554"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,2,28]]},"abstract":"<jats:p>We introduce and study a general scheduling problem that we term the Polytope Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes, and the rates assigned by the scheduler to the jobs are subject to arbitrary packing constraints. The PSP framework captures a variety of scheduling problems, including the classical problems of unrelated machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling.<\/jats:p>\n          <jats:p>\n            We show a surprising result\u2014there is a\n            <jats:italic>single<\/jats:italic>\n            algorithm that is\n            <jats:italic>O<\/jats:italic>\n            (1) competitive for\n            <jats:italic>all<\/jats:italic>\n            PSP instances when the objective is total completion time, and\n            <jats:italic>O<\/jats:italic>\n            (1) competitive for a large sub-class of PSP instances when the objective is total flow time. This algorithm simply uses the well-known Proportional Fairness (PF) algorithm to perform allocations each time instant. Though P\n            <jats:sc>F<\/jats:sc>\n            has been extensively studied in the context of maximizing fairness in resource allocation, we present the\n            <jats:italic>first<\/jats:italic>\n            analysis in adversarial and general settings for optimizing job latency. Further, P\n            <jats:sc>F<\/jats:sc>\n            is non-clairvoyant, meaning that the algorithm doesn\u2019t need to know jobs sizes until their completion. We establish our positive results by making novel connections with Economics, in particular, the notions of market clearing, Gross Substitutes, and Eisenberg-Gale markets.\n          <\/jats:p>\n          <jats:p>\n            We complement these positive results with a negative result: We show that for the total flow time objective, any non-clairvoyant algorithm for\n            <jats:italic>general<\/jats:italic>\n            PSP has a strong lower bound on the competitive ratio unless given a poly-logarithmic speed augmentation. This motivates the need to consider sub-classes of PSP when studying flow time. The sub-class for which we obtain positive results not only captures several well-studied models, such as scheduling with speedup curves and related machine scheduling, but also captures as special cases hitherto unstudied scheduling problems, such as single source flow routing, routing multicast (video-on-demand) trees, and resource allocation with substitute resources.\n          <\/jats:p>","DOI":"10.1145\/3136754","type":"journal-article","created":{"date-parts":[[2017,12,13]],"date-time":"2017-12-13T14:50:37Z","timestamp":1513176637000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Competitive Algorithms from Competitive Equilibria"],"prefix":"10.1145","volume":"65","author":[{"given":"Sungjin","family":"Im","sequence":"first","affiliation":[{"name":"University of California, Merced, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Janardhan","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kamesh","family":"Munagala","sequence":"additional","affiliation":[{"name":"Duke University, Durham NC"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/98.475988"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2189750.2150984"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.811450"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095213"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627823"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133117"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496904"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634079"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/060674417"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880954"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-004-0514-4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0888"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-006-7587-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press New York NY.   Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-008-9144-x"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536506"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9349-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007411"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482582"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. 1123--1140","author":"Nikhil"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022952324290"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133045"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229172"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_17"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627885"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627827"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.42"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI).","author":"Ghodsi Ali","year":"2011"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095214"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 10th International Workshop on Approximation and Online Algorithms (WAOA). 173--186","author":"Gupta Anupam","year":"2012"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789945.2789946"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591814"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.38"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.63"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344429"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998037.1998058"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_41"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.11.011"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-009-9143-8"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Frank P. Kelly Aman K. Maulloo and David K. H. Tan. 1998. Rate control for communication networks: Shadow prices proportional fairness and stability. J. Operat. Res. Soc. (1998) 237--252.  Frank P. Kelly Aman K. Maulloo and David K. H. Tan. 1998. Rate control for communication networks: Shadow prices proportional fairness and stability. J. Operat. Res. Soc. (1998) 237--252.","DOI":"10.1038\/sj.jors.2600523"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 3rd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud\u201911)","volume":"11","author":"Lee Gunho"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585506"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907266"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2342356.2342396"},{"key":"e_1_2_1_49_1","unstructured":"Kirk Pruhs Jiri Sgall and Eric Torng. 2004. Handbook of Scheduling: Algorithms Models and Performance Analysis. Joseph Y.-T. Leung (ed.). CRC Press 15--1.   Kirk Pruhs Jiri Sgall and Eric Torng. 2004. Handbook of Scheduling: Algorithms Models and Performance Analysis. Joseph Y.-T. Leung (ed.). CRC Press 15--1."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00251-1"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 491--500","author":"Robert Julien","year":"2008"},{"key":"e_1_2_1_52_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency.","author":"Schrijver Alexander","year":"2003"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM\u201997)","author":"Andreas"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2010.5496972"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2727(76)90018-9"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press. I--XI 1--504 pages.   David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press. I--XI 1--504 pages.","DOI":"10.1017\/CBO9780511921735"},{"key":"e_1_2_1_57_1","volume-title":"Flex: A slot allocation scheduling optimizer for mapreduce workloads. In Middleware","author":"Wolf Joel","year":"2010"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.16350"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201908)","author":"Zaharia Matei","year":"2008"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u201914)","author":"Zahedi Seyed Majid"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3136754","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3136754","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3136754","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:37Z","timestamp":1750212817000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3136754"}},"subtitle":["Non-Clairvoyant Scheduling under Polyhedral Constraints"],"short-title":[],"issued":{"date-parts":[[2017,12,11]]},"references-count":60,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2,28]]}},"alternative-id":["10.1145\/3136754"],"URL":"https:\/\/doi.org\/10.1145\/3136754","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,11]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}