{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:13Z","timestamp":1740109573590,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"h2020 european research council","doi-asserted-by":"publisher","award":["947778"],"award-info":[{"award-number":["947778"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"engineering and physical sciences research council","doi-asserted-by":"publisher","award":["EP\/S016694\/1"],"award-info":[{"award-number":["EP\/S016694\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0\/1 polytopes and half-integral polytopes.<\/jats:p>","DOI":"10.1007\/s00454-022-00406-8","type":"journal-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T14:04:51Z","timestamp":1657029891000},"page":"975-990","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Counting Vertices of Integral Polytopes Defined by Facets"],"prefix":"10.1007","volume":"70","author":[{"given":"Heng","family":"Guo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0863-7279","authenticated-orcid":false,"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"406_CR1","doi-asserted-by":"crossref","unstructured":"Anari, N., Liu, K., Gharan, S.O., Vinzant, C.: Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid. In: 51st Annual ACM SIGACT Symposium on Theory of Computing (Phoenix 2019), pp. 1\u201312. ACM, New York (2019)","DOI":"10.1145\/3313276.3316385"},{"issue":"3\u20134","key":"406_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0020-0190(00)00011-9","volume":"73","author":"D Avis","year":"2000","unstructured":"Avis, D., Devroye, L.: Estimating the number of vertices of a polyhedron. Inf. Process. Lett. 73(3\u20134), 137\u2013143 (2000)","journal-title":"Inf. Process. Lett."},{"key":"406_CR3","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1287\/mnsc.12.3.253","volume":"12","author":"ML Balinski","year":"1965","unstructured":"Balinski, M.L.: Integer programming: methods, uses, computation. Manage. Sci. 12, 253\u2013313 (1965)","journal-title":"Manage. Sci."},{"key":"406_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2012.02.029","volume":"437","author":"P Chebolu","year":"2012","unstructured":"Chebolu, P., Goldberg, L.A., Martin, R.: The complexity of approximately counting stable matchings. Theoret. Comput. Sci. 437, 35\u201368 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"406_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/j.jcss.2014.06.006","volume":"81","author":"X Chen","year":"2015","unstructured":"Chen, X., Dyer, M., Goldberg, L.A., Jerrum, M., Lu, P., McQuillan, C., Richerby, D.: The complexity of approximating conservative counting CSPs. J. Comput. System Sci. 81(1), 311\u2013329 (2015)","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"406_CR6","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s10107-007-0103-y","volume":"114","author":"G Ding","year":"2008","unstructured":"Ding, G., Feng, L., Zang, W.: The complexity of recognizing linear systems with certain integrality properties. Math. Program. 114(2), 321\u2013334 (2008)","journal-title":"Math. Program."},{"issue":"3","key":"406_CR7","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00453-003-1073-y","volume":"38","author":"M Dyer","year":"2004","unstructured":"Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: The relative complexity of approximate counting problems. Algorithmica 38(3), 471\u2013500 (2004)","journal-title":"Algorithmica"},{"key":"406_CR8","doi-asserted-by":"crossref","unstructured":"Huang, L., Lu, P., Zhang, Ch.: Canonical paths for MCMC: from art to science. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington 2016), pp. 514\u2013527. ACM, New York (2016)","DOI":"10.1137\/1.9781611974331.ch38"},{"issue":"4","key":"406_CR9","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1145\/1008731.1008738","volume":"51","author":"M Jerrum","year":"2004","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51(4), 671\u2013697 (2004)","journal-title":"J. ACM"},{"issue":"2\u20133","key":"406_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"MR Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43(2\u20133), 169\u2013188 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"406_CR11","doi-asserted-by":"crossref","unstructured":"Khachiyan, L.: Transversal hypergraphs and families of polyhedral cones. In: Advances in Convex Analysis and Global Optimization (Pythagorion 2000). Nonconvex Optim. Appl., vol. 54, pp. 105\u2013118. Kluwer, Dordrecht (2001)","DOI":"10.1007\/978-1-4613-0279-7_5"},{"issue":"2","key":"406_CR12","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1287\/moor.1070.0286","volume":"33","author":"T Kir\u00e1ly","year":"2008","unstructured":"Kir\u00e1ly, T., Pap, J.: Total dual integrality of Rothblum\u2019s description of the stable-marriage polyhedron. Math. Oper. Res. 33(2), 283\u2013290 (2008)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"406_CR13","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/990518.990521","volume":"7","author":"MS Krishnamoorthy","year":"1975","unstructured":"Krishnamoorthy, M.S.: An NP-hard problem in bipartite graphs. SIGACT News 7(1), 26 (1975)","journal-title":"SIGACT News"},{"key":"406_CR14","unstructured":"Mihail, M., Vazirani, U.: On the magnification of $$0$$-$$1$$ polytopes. Technical report TR-03-89, Harvard University (1989)"},{"key":"406_CR15","unstructured":"Najt, E.: The intractability of uniformly sampling and counting the vertices of a polytope (2019)"},{"issue":"1","key":"406_CR16","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02122701","volume":"10","author":"CH Papadimitriou","year":"1990","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On recognizing integer polyhedra. Combinatorica 10(1), 107\u2013109 (1990)","journal-title":"Combinatorica"},{"key":"406_CR17","doi-asserted-by":"crossref","unstructured":"Salomone, R., Vaisman, R., Kroese, D.: Estimating the number of vertices in convex polytopes. In: 4th Annual International Conference on Operations Research and Statistics (Singapore 2016), pp. 96\u2013105. Global Science & Technology Forum, Singapore (2016)","DOI":"10.5176\/2251-1938_ORS16.25"},{"key":"406_CR18","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Vol.\u00a0A. Paths, Flows, Matchings. Algorithms and Combinatorics, vol.\u00a024A. Springer, Berlin (2003)"},{"issue":"3","key":"406_CR19","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0095-8956(80)90075-1","volume":"28","author":"PD Seymour","year":"1980","unstructured":"Seymour, P.D.: Decomposition of regular matroids. J. Combin. Theory Ser. B 28(3), 305\u2013359 (1980)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"406_CR20","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1137\/0214060","volume":"14","author":"L Stockmeyer","year":"1985","unstructured":"Stockmeyer, L.: On approximation algorithms for $$\\#{\\rm P}$$. SIAM J. Comput. 14(4), 849\u2013861 (1985)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"406_CR21","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0095-8956(90)90030-4","volume":"49","author":"K Truemper","year":"1990","unstructured":"Truemper, K.: A decomposition theory for matroids. V. Testing of matrix total unimodularity. J. Combin. Theory Ser. B 49(2), 241\u2013281 (1990)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"406_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189\u2013201 (1979)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"406_CR23","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theoret. Comput. Sci. 47(1), 85\u201393 (1986)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"406_CR24","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0167-6377(89)90041-2","volume":"8","author":"JH Vande Vate","year":"1989","unstructured":"Vande Vate, J.H.: Linear programming brings marital bliss. Oper. Res. Lett. 8(3), 147\u2013153 (1989)","journal-title":"Oper. Res. Lett."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00406-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00406-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00406-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T17:03:15Z","timestamp":1696438995000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00406-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["406"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00406-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,7,5]]},"assertion":[{"value":"20 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}