{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:07Z","timestamp":1781031427823,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1955173"],"award-info":[{"award-number":["CCF-1955173"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["ECCS-2216899"],"award-info":[{"award-number":["ECCS-2216899"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800877","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1692-1703","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3114-3947","authenticated-orcid":false,"given":"Yury","family":"Makarychev","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the Symposium on Theory of Computing. 573\u2013581","author":"Agarwal Amit","year":"2005","unstructured":"Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. 2005. O(\u221a log n) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. In Proceedings of the Symposium on Theory of Computing. 573\u2013581."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0272-6"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the International Workshop on Approximation and Online Algorithms. 27\u201340","author":"Avidor Adi","year":"2005","unstructured":"Adi Avidor, Ido Berkovitch, and Uri Zwick. 2005. Improved approximation algorithms for Max NAE-SAT and Max SAT. In Proceedings of the International Workshop on Approximation and Online Algorithms. 27\u201340."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4171\/jems\/993"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451003"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718127"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1740582.1740583"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00023"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.53"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132547"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.65"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541893"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.36"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195296221"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756144"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_14"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.01.004"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.09.003"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01058727"},{"key":"e_1_3_2_1_25_1","volume-title":"Probabilistic symmetries and invariance principles","author":"Kallenberg Olav","unstructured":"Olav Kallenberg. 2005. Probabilistic symmetries and invariance principles. Springer."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591817"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47867-1_6"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the International Symposium on Theoretical Aspects of Computer Science. 139","author":"Makarychev Konstantin","year":"2013","unstructured":"Konstantin Makarychev. 2013. Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs. In Proceedings of the International Symposium on Theoretical Aspects of Computer Science. 139."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_22"},{"key":"e_1_3_2_1_30_1","volume-title":"Andrei Krokhin and Stanislav Zivny (Eds.) (Dagstuhl Follow-Ups","volume":"325","author":"Makarychev Konstantin","year":"2017","unstructured":"Konstantin Makarychev and Yury Makarychev. 2017. Approximation Algorithms for CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav Zivny (Eds.) (Dagstuhl Follow-Ups, Vol. 7). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 287\u2013325."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.64"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2012.08.008"},{"key":"e_1_3_2_1_33_1","unstructured":"Yury Makarychev. 2026. Approximation Algorithms for Satisfiable and Nearly Satisfiable Ordering CSPs. arxiv:2603.30020."},{"key":"e_1_3_2_1_34_1","unstructured":"Yury Makarychev. 2026. Ordering Constraint Satisfaction Problems (arity 4). https:\/\/github.com\/ymakarychev\/ordering-csp GitHub repository"},{"key":"e_1_3_2_1_35_1","first-page":"116","article-title":"A combinatorial problem of finite sequences","volume":"16","author":"Niven Ivan","year":"1968","unstructured":"Ivan Niven. 1968. A combinatorial problem of finite sequences. Nieuw Arch. Wisk, 16, 3 (1968), 116\u2013123.","journal-title":"Nieuw Arch. Wisk"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1090\/spmj\/1473"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010035"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276869"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800877","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:59:31Z","timestamp":1781027971000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":43,"alternative-id":["10.1145\/3798129.3800877","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800877","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}