{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:36Z","timestamp":1760202576863},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":5490,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1993,9]]},"abstract":"<jats:p>We describe a <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000675inline1\" \/> time randomized algorithm that estimates the number of feasible solutions of a multidimensional knapsack problem within 1 \u00b1 <jats:italic>\u03b5<\/jats:italic> of the exact number. (Here <jats:italic>r<\/jats:italic> is the number of constraints and <jats:italic>n<\/jats:italic> is the number of integer variables.) The algorithm uses a Markov chain to generate an almost uniform random solution to the problem.<\/jats:p>","DOI":"10.1017\/s0963548300000675","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:18:58Z","timestamp":1221218338000},"page":"271-284","source":"Crossref","is-referenced-by-count":33,"title":["A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem"],"prefix":"10.1017","volume":"2","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[]},{"given":"Ravi","family":"Kannan","sequence":"additional","affiliation":[]},{"given":"Ajai","family":"Kapoor","sequence":"additional","affiliation":[]},{"given":"Ljubomir","family":"Perkovic","sequence":"additional","affiliation":[]},{"given":"Umesh","family":"Vazirani","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300000675_ref011","volume-title":"Combinatorial problems and exercises","author":"Lov\u00e1sz","year":"1979"},{"key":"S0963548300000675_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"S0963548300000675_ref002","first-page":"50","article-title":"How hard is it to marry at random?","author":"Broder","year":"1986","journal-title":"Proceedings of the 18th Annual ACM Symposium on Theory of Computing"},{"key":"S0963548300000675_ref009","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267759"},{"key":"S0963548300000675_ref014","first-page":"138","article-title":"On the number of Euler orientations of a graph","author":"Mihail","year":"1992","journal-title":"Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"S0963548300000675_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"S0963548300000675_ref004","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"S0963548300000675_ref003","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/044\/1141926"},{"key":"S0963548300000675_ref010","unstructured":"[10] Karzanov A. and Khachiyan L. (1990) On the conductance of order Markov chains. Technical Report DCS TR 268, Rutgers University."},{"key":"S0963548300000675_ref001","first-page":"156","article-title":"Sampling and integration of near log-concave functions","author":"Applegate","year":"1991","journal-title":"Proc. 23rd ACM Symposium on Theory of Computing"},{"key":"S0963548300000675_ref006","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"S0963548300000675_ref012","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1109\/FSCS.1990.89553","article-title":"The mixing rate of Markov chains, an isoperimetric inequality and computing the volume","author":"Lov\u00e1sz","year":"1990","journal-title":"Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science"},{"key":"S0963548300000675_ref007","unstructured":"[7] Jerrum M. R. and Sinclair A. J. (1989) Polynomial-time approximation algorithms for the Ising model, Department of Computer Science, Edinburgh University. (To appear in SIAM Journal on Computing.)"},{"key":"S0963548300000675_ref013","unstructured":"[13] Lov\u00e1sz L. and Simonovits M. (1992) Random walks in a convex body and an improved volume algorithm. Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science."},{"key":"S0963548300000675_ref005","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300000675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T21:57:52Z","timestamp":1557957472000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300000675\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,9]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,9]]}},"alternative-id":["S0963548300000675"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300000675","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,9]]}}}