{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:46Z","timestamp":1787337466409,"version":"build-2736575974"},"reference-count":82,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension.<\/jats:p>\n                  <jats:p>On the negative side, we present several $#\\P$-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is $#\\P$-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy.<\/jats:p>\n                  <jats:p>On the positive side, we derive a randomized algorithm for computing the mixed volumes $$ V(\\overbrace{K_1\\ld K_1}^{m_1}, \\overbrace{K_2,\\dots,K_2}^{m_2},\\dots,\\overbrace{K_s,\\dots,K_s}^{m_s}) $$ of well-presented convex bodies $K_1,\\dots,K_s$, where $m_1,\\dots,m_s \\in \\N_0$ and $m_1 \\geq n-\\psi(n)$ with $\\psi(n)=o(\\frac{\\log n}{\\log \\log n})$. The algorithm is an interpolation method based on polynomial-time randomized algorithms for computing the volume of convex bodies.<\/jats:p>\n                  <jats:p>This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.<\/jats:p>","DOI":"10.1137\/s0097539794278384","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"356-400","source":"Crossref","is-referenced-by-count":41,"title":["On The Complexity of Computing Mixed Volumes"],"prefix":"10.1137","volume":"27","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Gritzmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Hufnagel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","first-page":"1205","volume":"2","author":"Aleksandrov A. D.","year":"1937","journal-title":"Math. Sb. N.S."},{"key":"R2","first-page":"227","volume":"3","author":"Aleksandrov A. D.","year":"1938","journal-title":"Math. Sb. N.S."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1986-0815838-7"},{"key":"R4","unstructured":"D. Applegate and R. Kannan,\n                      Sampling and integration of near log\u2010concave functions\n                      , Proc. 23rd ACM Symp. Th. of Comput., 1990, pp. 156\u2013163."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187886"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.4.769"},{"key":"R7","unstructured":"I. S. Berezin and N. P. Zhidkov,\n                      Computing Methods\n                      , Vol. 1 Pergamon Press, Oxford, 1965."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01075595"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189930"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573960"},{"key":"R11","unstructured":"T. Bonnesen and W. Fenchel,\n                      Theorie der konvexen K\u00f6rper\n                      , Springer, Berlin, 1934;"},{"key":"R11","unstructured":"(reprinted: Chelsea, New York) 1948;"},{"key":"R11","unstructured":"Theory of Convex Bodies\n                      , (English edition), BCS Associates, Moscow, Idaho, U.S.A., 1987."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF00383444"},{"key":"R13","unstructured":"A. Z. Broder.\n                      How hard is it to marry at random? (On the approximation of the permanent)\n                      , Proc. 18th ACM Symp. Th. Comput., 1986, pp. 50\u201358."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(83)90050-2"},{"key":"R15","unstructured":"Yu. D. Burago and V. A. Zalgaller,\n                      Geometric Inequalities\n                      , Springer, Berlin, 1988."},{"key":"R16","unstructured":"John Canny, Ioannis Emiris, An efficient algorithm for the sparse mixed resultant, Lecture Notes in Comput. Sci., Vol. 673, Springer, Berlin, 1993, 89\u201310494m:12010"},{"key":"R17","unstructured":"J. Canny and J. M. Rojas,\n                      An optimality condition for determining the exact number of roots of a polynomial system\n                      in Proc. ACM Intern Symp. Algebraic Symbolic Comput. (Bonn, Germany), ACM Press, 1991, pp. 96\u2010102."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322141"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0714050"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90006-2"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"key":"R22","unstructured":"Martin Dyer, Alan Frieze, Computing the volume of convex bodies: a case where randomness provably helps, Proc. Sympos. Appl. Math., Vol. 44, Amer. Math. Soc., Providence, RI, 1991, 123\u201316993a:52004"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"R24","unstructured":"M. E. Dyer and R. Kannan,\n                      On Barvinok\u2019s algorithm for counting lattice points in fixed dimension\n                      , Math. Oper. Res., 1996, to appear."},{"key":"R25","unstructured":"J. Edmonds,\n                      Submodular functions, matroids, and certain polyhedra\n                      , in Combinatorial Structures and their Applications, (ed. by R. Guy, H. Hanani, N. Sauer and J. Sch\u00f6nheim), Gordon and Breach New York, 1970, pp. 69\u201387."},{"key":"R26","first-page":"1","volume":"226","author":"Ehrhart E.","year":"1967","journal-title":"J. reine angew. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0075-4102","issn-type":"print"},{"key":"R27","unstructured":"E. Ehrhart,\n                      Polyn\u00f4mes arithm\u00e9tiques et m\u00e9thode des poly\u00e9dres en combinatoire\n                      , Birkh\u00e4user, Basel, 1977."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1995.1041"},{"key":"R29","unstructured":"I. Z. Emiris and A. Rege,\n                      Monomial bases and polynomial system solving\n                      , in Proc. 8th ACM Intern Symp. Algebraic Symbolic Comput. \u201994, (Oxford, UK), ACM Press, 1994, pp. XXX\u2013XXX."},{"key":"R30","first-page":"647","volume":"203","author":"Fenchel W.","year":"1936","journal-title":"C. R. Acad. Sci. Paris"},{"key":"R31","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability\n                      , Freeman, San Francisco, 1979."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(90)90047-Q"},{"key":"R33","unstructured":"D. Girad and P. Valentin,\n                      Zonotopes and mixture management\n                      , New Methods in Optimization and their Industrial Uses, (ed. by J. P. Penot), ISNM87, Birkh\u00e4user, Basel, 1989, pp. 57\u201371."},{"key":"R34","unstructured":"Peter Gritzmann, Victor Klee, On the complexity of some basic problems in computational convexity. II. Volume and mixed volumes, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Vol. 440, Kluwer Acad. Publ., Dordrecht, 1994, 373\u201346696k:52012"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574058"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/0406019"},{"key":"R37","unstructured":"P. Gritzmann and J. M. Wills,\n                      Lattice points\n                      , in Handbook of Convex Geometry, (ed. by P. M. Gruber and J. M. Wills), Amsterdam, 1993, pp. 765\u2013798."},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1995-1297471-4"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"R42","unstructured":"D. S. Johnson,\n                      A catalog of complexity classes\n                      , Handbook of Theoretical Computer Science. vol. A: Algorithms and Complexity, (J. van Leeuwen, ed.), Elsevier and M. I. T. Press, Amsterdam and Cambridge, Mass., 1990, pp. 67\u2013161."},{"key":"R43","unstructured":"R. Kannan, L. Lov\u00e1sz, and M. Simonivits,\n                      Random walks and an O*(n5) volume algorithm for convex bodies\n                      , 1996, pp. XXX\u2013XXX."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/0222021"},{"key":"R45","unstructured":"Leonid Khachiyan, Complexity of polytope volume computation, Algorithms Combin., Vol. 10, Springer, Berlin, 1993, 91\u201310194m:68190"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582144"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1991-1079024-2"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1996.0009"},{"key":"R49","unstructured":"L. Lov\u00e1sz,\n                      Random walks on graphs: A survey\n                      , in Combinatorics: Paul Erd\u00f6s is 80, Vol. II, (ed. by D. Mikl\u00f3s, V. T. S\u00f3s and T. Sz\u00f6nyi), Bolyai Society, Budapest, 1995."},{"key":"R50","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz, Mikl\u00f3s Simonovits, The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 346\u201335493e:68035"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040402"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300002850"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(85)90031-1"},{"key":"R54","unstructured":"H. Minkowski,\n                      Theorie der konvexen K\u00f6rper, insbesondere Begr\u00fcndung ihres Oberfl\u00e4chenbegriffs\n                      , in Ges. Abh. Bd. II, Leipzig u. Berlin, 1911, pp. 131\u2013229."},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.2307\/2323259"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1986-0842135-6"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122701"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1007\/BF02572411"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1137\/0712053"},{"key":"R60","unstructured":"T. J. Rivlin,\n                      Chebyshev polynomials. From approximation theory to algebra and number theory\n                      , (2nd ed.), Wiley, New York, 1990."},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)00062-A"},{"key":"R62","unstructured":"J. M. Rojas,\n                      Toric intersection for affine root counting\n                      , 1996, pp. manuscript."},{"key":"R63","unstructured":"T. Y. Li, J. M. Rojas, and X. Wang,\n                      Counting affine roots of polynomial systems via pointed Newton polytopes\n                      , J. Complexity, 1994, pp. manuscript."},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0368391-0"},{"key":"R65","unstructured":"J. R. Sangwine\u2010Yager,\n                      Mixed volumes\n                      , in Handbook of Convex Geometry, (ed. by P. M. Gruber and J. M. Wills), Amsterdam, 1993, pp. 43\u201372."},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511526282"},{"key":"R67","unstructured":"R. Schneider,\n                      Polytopes and Brunn\u2010Minkowski theory\n                      , in Polytopes: Abstract, Convex and Computational, (ed. by T. Bisztriczky, P. McMullen, R. Schneider and A. Ivic Weiss), Kluwer, Boston, 1994, pp. 273\u2013300."},{"key":"R68","unstructured":"A. Schrijver,\n                      Linear and Integer Programming\n                      , Wiley\u2010Interscience, New York, 1986."},{"key":"R69","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1974-032-5"},{"key":"R70","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"R71","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(81)90053-4"},{"key":"R72","unstructured":"R. M. Stanley,\n                      Enumerative Combinatorics\n                      , Vol. 1, Wadsworth & Brooks\/Cole, Pacific Grove, CA, 1986."},{"key":"R73","unstructured":"Richard Stanley, A zonotope associated with graphical degree sequences, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 4, Amer. Math. Soc., Providence, RI, 1991, 555\u201357092k:52020"},{"key":"R74","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"R75","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"R76","doi-asserted-by":"publisher","DOI":"10.1007\/BF01385861"},{"key":"R77","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1995.1005"},{"key":"R78","doi-asserted-by":"publisher","DOI":"10.1137\/0731049"},{"key":"R79","unstructured":"D. J. A. Welsh,\n                      Matroid Theory\n                      , Academic Press, London, 1976."},{"key":"R80","unstructured":"N. White,\n                      Unimodular matroids\n                      , in Combinatorial Geometries, (ed. by N. White) Cambridge University Press, 1987, pp. 40\u201352."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794278384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:05Z","timestamp":1787335925000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794278384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":82,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794278384"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794278384","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}