{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T23:46:04Z","timestamp":1789688764668,"version":"4.0.1"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["I-1366-407.6\/2016"],"award-info":[{"award-number":["I-1366-407.6\/2016"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2015-06163"],"award-info":[{"award-number":["RGPIN-2015-06163"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006260","name":"Technion-Israel Institute of Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006260","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We introduce and study the problem of optimizing arbitrary functions over degree sequences of hypergraphs and multihypergraphs. We show that over multihypergraphs the problem can be solved in polynomial time. For hypergraphs, we show that deciding whether a given sequence is the degree sequence of a 3-hypergraph is NP-complete, thereby solving a 30 year long open problem. This implies that optimization over hypergraphs is hard even for simple concave functions. In contrast, we show that for graphs, if the functions at vertices are the same, then the problem is polynomial time solvable. We also provide positive results for convex optimization over multihypergraphs and graphs and exploit connections to degree sequence polytopes and threshold graphs. We then elaborate on connections to the emerging theory of shifted combinatorial optimization.<\/jats:p>","DOI":"10.1137\/17m1134482","type":"journal-article","created":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T11:37:57Z","timestamp":1533641877000},"page":"2067-2079","source":"Crossref","is-referenced-by-count":30,"title":["Optimization over Degree Sequences"],"prefix":"10.1137","volume":"32","author":[{"given":"Antoine","family":"Deza","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Syed M.","family":"Meesum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shmuel","family":"Onn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"D. Billington,\n                      Degree Multisets of Hypergraphs\n                      , Ph.D. thesis, University of Melbourne, 1982.","DOI":"10.1017\/S0004972700005955"},{"key":"atypb2","first-page":"71","volume":"3","author":"Billington D.","year":"1988","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90028-4"},{"key":"atypb4","first-page":"264","volume":"11","author":"Erdo\u0308s P.","year":"1960","journal-title":"Mat. Lopak"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000096"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62389-4_19"},{"key":"atypb7","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability\n                      , Freeman, 1979."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Gro\u0308tschel, L. Lova\u0301sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Springer, 1993.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/0110037"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.21136\/CPM.1955.108220"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2015.09.005"},{"key":"atypb12","doi-asserted-by":"crossref","first-page":"14","DOI":"10.37236\/738","volume":"15","author":"Klivans C.","year":"2008","journal-title":"Electron. J. Combin."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(73)90037-3"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.401"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2016.05.013"},{"key":"atypb17","first-page":"1","volume":"20","author":"Liu R. I.","year":"2013","journal-title":"Electron. J. Combin."},{"key":"atypb18","unstructured":"N. V. R. Mahadev and U. N Peled,\n                      Threshold Graphs and Related Topics\n                      , Ann. Discrete Math. 56, North-Holland, 1995."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00272-0"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199908)31:4<283::AID-JGT3>3.0.CO;2-H"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(89)90470-9"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1957-044-3"},{"key":"atypb23","unstructured":"A. Schrijver,\n                      Combinatorial Optimization\n                      , Springer, 2003."},{"key":"atypb24","unstructured":"D. B. West,\n                      Introduction to Graph Theory\n                      , Prentice-Hall, 1996."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1134482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:13Z","timestamp":1787320753000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1134482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1134482"],"URL":"https:\/\/doi.org\/10.1137\/17m1134482","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}