{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:12:21Z","timestamp":1743142341472,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030261757"},{"type":"electronic","value":"9783030261764"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-26176-4_3","type":"book-chapter","created":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T23:02:56Z","timestamp":1563922976000},"page":"25-37","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An FPTAS for a General Class of Parametric Optimization Problems"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arne","family":"Herzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clemens","family":"Thielen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Vanderpooten","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,21]]},"reference":[{"key":"3_CR1","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993)"},{"issue":"1","key":"3_CR2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0166-218X(93)90245-J","volume":"41","author":"T Arai","year":"1993","unstructured":"Arai, T., Ueno, S., Kajitani, Y.: Generalization of a theorem on the parametric maximum flow problem. Discrete Appl. Math. 41(1), 69\u201374 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BF02591893","volume":"26","author":"PJ Carstensen","year":"1983","unstructured":"Carstensen, P.J.: Complexity of some parametric integer and network programming problems. Math. Program. 26(1), 64\u201375 (1983)","journal-title":"Math. Program."},{"key":"3_CR4","unstructured":"Carstensen, P.J.: The complexity of some problems in parametric, linear, and combinatorial programming. Ph.D. thesis, University of Michigan (1983)"},{"issue":"4","key":"3_CR5","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1145\/321978.321982","volume":"23","author":"MJ Eisner","year":"1976","unstructured":"Eisner, M.J., Severance, D.G.: Mathematical techniques for efficient record segmentation in large shared databases. J. ACM 23(4), 619\u2013635 (1976)","journal-title":"J. ACM"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-61422-2_128","volume-title":"Algorithm Theory \u2014 SWAT\u201996","author":"D Fern\u00e1ndez-Baca","year":"1996","unstructured":"Fern\u00e1ndez-Baca, D., Slutzki, G., Eppstein, D.: Using sparsification for parametric minimum spanning tree problems. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 149\u2013160. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61422-2_128"},{"issue":"1","key":"3_CR7","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1), 30\u201355 (1989)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"3_CR8","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/net.20288","volume":"55","author":"E Gassner","year":"2010","unstructured":"Gassner, E., Klinz, B.: A fast parametric assignment algorithm with applications in max-algebra. Networks 55(2), 61\u201377 (2010)","journal-title":"Networks"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.ipl.2016.12.003","volume":"120","author":"A Giudici","year":"2017","unstructured":"Giudici, A., Halffmann, P., Ruzika, S., Thielen, C.: Approximation schemes for the parametric knapsack problem. Inf. Process. Lett. 120, 11\u201315 (2017)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"3_CR10","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/j.orl.2018.07.005","volume":"46","author":"N Halman","year":"2018","unstructured":"Halman, N., Holzhauser, M., Krumke, S.O.: An FPTAS for the knapsack problem with parametric weights. Oper. Res. Lett. 46(5), 487\u2013491 (2018)","journal-title":"Oper. Res. Lett."},{"key":"3_CR11","unstructured":"Hertrich, C.: A parametric view on robust graph problems. Bachelor\u2019s thesis, University of Kaiserslautern, August 2016"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.ipl.2017.06.006","volume":"126","author":"M Holzhauser","year":"2017","unstructured":"Holzhauser, M., Krumke, S.O.: An FPTAS for the parametric knapsack problem. Inf. Process. Lett. 126, 43\u201347 (2017)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"3_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","volume":"3","author":"RM Karp","year":"1981","unstructured":"Karp, R.M., Orlin, J.B.: Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl. Math. 3(1), 37\u201345 (1981)","journal-title":"Discrete Appl. Math."},{"key":"3_CR14","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E Lawler","year":"2001","unstructured":"Lawler, E.: Combinatorial Optimization: Networks and Matroids. Dover Publications, New York (2001)"},{"issue":"5","key":"3_CR15","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1287\/opre.47.5.744","volume":"47","author":"ST McCormick","year":"1999","unstructured":"McCormick, S.T.: Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Oper. Res. 47(5), 744\u2013756 (1999)","journal-title":"Oper. Res."},{"issue":"3","key":"3_CR16","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1016\/j.ejor.2008.01.007","volume":"194","author":"A Mitsos","year":"2009","unstructured":"Mitsos, A., Barton, P.I.: Parametric mixed-integer 0\u20131 linear programming: the general case for a single parameter. Eur. J. Oper. Res. 194(3), 663\u2013686 (2009)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1006\/jcss.2001.1766","volume":"63","author":"K Mulmuley","year":"2001","unstructured":"Mulmuley, K., Shah, P.: A lower bound for the shortest path problem. J. Comput. Syst. Sci. 63(2), 253\u2013267 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"3_CR18","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/BF01581642","volume":"19","author":"K Murty","year":"1980","unstructured":"Murty, K.: Computational complexity of parametric linear programming. Math. Program. 19(1), 213\u2013219 (1980)","journal-title":"Math. Program."},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1007\/11841036_50","volume-title":"Algorithms \u2013 ESA 2006","author":"E Nikolova","year":"2006","unstructured":"Nikolova, E., Kelner, J.A., Brand, M., Mitzenmacher, M.: Stochastic shortest paths via quasi-convex maximization. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 552\u2013563. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11841036_50"},{"issue":"1","key":"3_CR20","first-page":"9","volume":"32","author":"G Ruhe","year":"1988","unstructured":"Ruhe, G.: Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh. Zeitschrift f\u00fcr Oper. Res. 32(1), 9\u201327 (1988)","journal-title":"Zeitschrift f\u00fcr Oper. Res."},{"key":"3_CR21","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24, 1st edn. Springer, Heidelberg (2003)","edition":"1"},{"issue":"1","key":"3_CR22","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10479-006-0155-z","volume":"150","author":"MG Scutell\u00e0","year":"2007","unstructured":"Scutell\u00e0, M.G.: A note on the parametric maximum flow problem and some related reoptimization issues. Ann. Oper. Res. 150(1), 231\u2013244 (2007)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"3_CR23","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230210206","volume":"21","author":"NE Young","year":"2006","unstructured":"Young, N.E., Tarjan, R.E., Orlin, J.B.: Faster parametric shortest path and minimum-balance algorithms. Networks 21(2), 205\u2013221 (2006)","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-26176-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T14:04:40Z","timestamp":1709820280000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-26176-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030261757","9783030261764"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-26176-4_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"21 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Xi'an","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2019a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ictt.xidian.edu.cn\/COCOON2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}