{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T11:16:39Z","timestamp":1725880599298},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319539249"},{"type":"electronic","value":"9783319539256"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-53925-6_33","type":"book-chapter","created":{"date-parts":[[2017,2,20]],"date-time":"2017-02-20T01:12:36Z","timestamp":1487553156000},"page":"421-432","source":"Crossref","is-referenced-by-count":1,"title":["An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths"],"prefix":"10.1007","author":[{"given":"Ei","family":"Ando","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,21]]},"reference":[{"key":"33_CR1","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1007\/s00453-015-0096-5","volume":"76","author":"E Ando","year":"2016","unstructured":"Ando, E., Kijima, S.: An FPTAS for the volume computation of $$0-1$$ knapsack polytopes based on approximate convolution. Algorithmica 76, 1245\u20131263 (2016)","journal-title":"Algorithmica"},{"key":"33_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-02017-9_13","volume-title":"Theory and Applications of Models of Computation","author":"E Ando","year":"2009","unstructured":"Ando, E., Ono, H., Sadakane, K., Yamashita, M.: Computing the exact distribution function of the stochastic longest path length in a DAG. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol. 5532, pp. 98\u2013107. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-02017-9_13"},{"key":"33_CR3","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF02187886","volume":"2","author":"I B\u00e1r\u00e1ny","year":"1987","unstructured":"B\u00e1r\u00e1ny, I., F\u00fcredi, Z.: Computing the volume is difficult. Discrete Comput. Geom. 2, 319\u2013326 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"33_CR4","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1109\/TCAD.2007.907047","volume":"27","author":"D Blaauw","year":"2008","unstructured":"Blaauw, D., Chopra, K., Srivastava, A., Scheffer, L.: Statistical timing analysis: from basic principles to state of the art. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 27, 589\u2013606 (2008)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst."},{"key":"33_CR5","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H Bodlaender","year":"1996","unstructured":"Bodlaender, H.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"Cousins, B., Vempala, S.: Bypassing KLS: Gaussian cooling and an $$O^\\ast (n^3)$$ volume algorithm. In: 47th Annual ACM Symposium on the Theory of Computing, pp. 539\u2013548. ACM, New York (2015)","DOI":"10.1145\/2746539.2746563"},{"key":"33_CR7","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1137\/0217060","volume":"17","author":"M Dyer","year":"1988","unstructured":"Dyer, M., Frieze, A.: On the complexity of computing the volume of a polyhedron. SIAM J. Comput. 17, 967\u2013974 (1988)","journal-title":"SIAM J. Comput."},{"key":"33_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM 38, 1\u201317 (1991)","journal-title":"J. ACM"},{"key":"33_CR9","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF02187701","volume":"1","author":"G Elekes","year":"1986","unstructured":"Elekes, G.: A geometric inequality and the complexity of computing volume. Discrete Comput. Geom. 1, 289\u2013292 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Klivans, A., Meka, R.: Polynomial-time approximation schemes for knapsack and related counting problems using branching programs. arXiv:1008.3187v1 (2010)","DOI":"10.1109\/FOCS.2011.32"},{"key":"33_CR11","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Klivans, A., Meka, R., \u0160tefankovi\u010d, D., Vempala, S., Vigoda, E.: An FPTAS for #knapsack and related counting problems. In: 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 817\u2013826. IEEE Publications, New York (2011)","DOI":"10.1109\/FOCS.2011.32"},{"key":"33_CR12","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Combin. Theory Ser. B 82, 138\u2013155 (2001)","journal-title":"J. Combin. Theory Ser. B"},{"key":"33_CR13","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.orl.2014.02.004","volume":"42","author":"J Li","year":"2014","unstructured":"Li, J., Shi, T.: A fully polynomial-time approximation scheme for approximating a sum of random variables. Oper. Res. Lett. 42, 197\u2013202 (2014)","journal-title":"Oper. Res. Lett."},{"key":"33_CR14","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970203","volume-title":"An Algorithmic Theory of Numbers, Graphs and Convexity","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L.: An Algorithmic Theory of Numbers, Graphs and Convexity. SIAM Society for Industrial and Applied Mathematics, Philadelphia (1986)"},{"key":"33_CR15","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.jcss.2005.08.004","volume":"72","author":"L Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz, L., Vempala, S.: Simulated annealing in convex bodies and an $$O^\\ast (n^4)$$ volume algorithm. J. Comput. Syst. Sci. 72, 392\u2013417 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"33_CR16","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1137\/11083976X","volume":"41","author":"D \u0160tefankovi\u010d","year":"2012","unstructured":"\u0160tefankovi\u010d, D., Vempala, S., Vigoda, E.: A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM J. Comput. 41, 356\u2013366 (2012)","journal-title":"SIAM J. Comput."},{"key":"33_CR17","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01580859","volume":"47","author":"P Vaidya","year":"1990","unstructured":"Vaidya, P.: An algorithm for linear programming which requires $$O(((m + n)n^2+ (m + n)^{1.5}n)L)$$ arithmetic operations. Math. Program. 47, 175\u2013201 (1990)","journal-title":"Math. Program."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53925-6_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T21:30:44Z","timestamp":1568842244000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53925-6_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319539249","9783319539256"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53925-6_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}