{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:37:47Z","timestamp":1725543467840},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540357537"},{"type":"electronic","value":"9783540357551"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_33","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T01:24:10Z","timestamp":1151285050000},"page":"351-362","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Rational Objectives Is as Easy as Approximating Linear Ones"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 R.","family":"Correa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristina G.","family":"Fernandes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshiko","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"33_CR1","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/S0167-6377(02)00157-8","volume":"30","author":"A. Billionnet","year":"2002","unstructured":"Billionnet, A.: Approximation algorithms for fractional knapsack problems. Operations Research Letters\u00a030(5), 336\u2013342 (2002)","journal-title":"Operations Research Letters"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1287\/opre.24.4.675","volume":"24","author":"G.R. Bitran","year":"1976","unstructured":"Bitran, G.R., Magnanti, T.L.: Duality and sensitivity analysis for fractional programs. Operations Research\u00a024, 675\u2013699 (1976)","journal-title":"Operations Research"},{"key":"33_CR3","unstructured":"Carlson, J., Eppstein, D.: The weighted maximum-mean subtree and other bicriterion subtree problems. In: ACM Computing Research Repository(2005) cs.CG\/0503023"},{"key":"33_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10878-005-5485-2","volume":"9","author":"D.Z. Chen","year":"2005","unstructured":"Chen, D.Z., Daescu, O., Dai, Y., Katoh, N., Wu, X., Xu, J.: Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications. Journal of Combinatorial Optimization\u00a09, 69\u201390 (2005)","journal-title":"Journal of Combinatorial Optimization"},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"Dantzig, G.B., Blattner, W., Rao, M.R.: Finding a cycle in a graph with minimum cost to time ratio with applications to a ship routing problem. In: Rosensthiel, P. (ed.) Theory of Graphs: Int.\u00a0Symposium, Dunod, Paris, pp. 77\u201384 (1967)","DOI":"10.21236\/AD0646553"},{"issue":"10","key":"33_CR6","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1109\/43.728912","volume":"17","author":"A. Dasdan","year":"1998","unstructured":"Dasdan, A., Gupta, R.K.: Faster maximum and minimum mean cycle algorithms for system-performance analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems\u00a017(10), 889\u2013899 (1998)","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Dasdan, A., Irani, S.S., Gupta, R.K.: Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems. In: Proceedings of the 36th ACM\/IEEE Conference on Design Automation, pp. 37\u201342 (1999)","DOI":"10.1145\/309847.309862"},{"key":"33_CR8","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1287\/mnsc.13.7.492","volume":"13","author":"W. Dinkelbach","year":"1967","unstructured":"Dinkelbach, W.: On nonlinear fractional programming. Management Science\u00a013, 492\u2013498 (1967)","journal-title":"Management Science"},{"key":"33_CR9","volume-title":"Computers and Intractability: a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York (1979)"},{"key":"33_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-540-24698-5_25","volume-title":"LATIN 2004: Theoretical Informatics","author":"P. Gubbala","year":"2004","unstructured":"Gubbala, P., Raghavachari, B.: Finding k-connected subgraphs with minimum average weight. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 212\u2013221. Springer, Heidelberg (2004)"},{"key":"33_CR11","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF02591737","volume":"37","author":"S. Hashizume","year":"1987","unstructured":"Hashizume, S., Fukushima, M., Katoh, N., Ibaraki, T.: Approximation algorithms for combinatorial fractional programming problems. Mathematical Programming\u00a037, 255\u2013267 (1987)","journal-title":"Mathematical Programming"},{"key":"33_CR12","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1287\/mnsc.12.7.609","volume":"12","author":"R. Jagannathan","year":"1966","unstructured":"Jagannathan, R.: On some properties of programming problems in parametric form pertaining to fractional programming. Management Science\u00a012, 609\u2013615 (1966)","journal-title":"Management Science"},{"issue":"1","key":"33_CR13","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K. Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica\u00a021(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"issue":"1","key":"33_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0196-6774(02)00222-5","volume":"45","author":"K. Jain","year":"2002","unstructured":"Jain, K., M\u0103ndoiu, I., Vazirani, V.V., Williamson, D.P.: A primal-dual schema based approximation algorithm for the element connectivity problem. Journal of Algorithms\u00a045(1), 1\u201315 (2002)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"33_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0166-218X(92)90038-C","volume":"35","author":"N. Katoh","year":"1992","unstructured":"Katoh, N.: A fully polynomial-time approximation scheme for minimum cost-reliability ratio problems. Discrete Applied Mathematics\u00a035(2), 143\u2013155 (1992)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"33_CR16","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/174652.174654","volume":"41","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. Journal of the Association for Computing Machinery\u00a041(2), 214\u2013235 (1994)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"33_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/978-3-540-39658-1_62","volume-title":"Algorithms - ESA 2003","author":"G. Klau","year":"2003","unstructured":"Klau, G., Ljubi, I., Mutzel, P., Pferschy, U., Weiskircher, R.: The fractional prize collecting Steiner tree problem on trees. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 691\u2013702. Springer, Heidelberg (2003)"},{"key":"33_CR18","unstructured":"Lawler, E.L.: Optimal cycles in doubly weighted directed linear graphs. In: Rosensthiel, P. (ed.) Theory of Graphs: Int.\u00a0Symposium, Dunod, Paris, pp. 209\u2013214 (1967)"},{"issue":"4","key":"33_CR19","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N. Megiddo","year":"1979","unstructured":"Megiddo, N.: Combinatorial optimization with rational objective functions. Mathematics of Operations Research\u00a04(4), 414\u2013424 (1979)","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"33_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01586040","volume":"54","author":"J.B. Orlin","year":"1992","unstructured":"Orlin, J.B., Ahuja, R.K.: New scaling algorithms for the assignment and minimum mean cycle problems. Mathematical Programming\u00a054(1), 41\u201356 (1992)","journal-title":"Mathematical Programming"},{"key":"33_CR21","doi-asserted-by":"crossref","unstructured":"Radzik, T.: Newton\u2019s method for fractional combinatorial optimization. In: Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 659\u2013669 (1992)","DOI":"10.1109\/SFCS.1992.267785"},{"issue":"2\u20133","key":"33_CR22","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0166-218X(93)00094-G","volume":"56","author":"M. Shigeno","year":"1995","unstructured":"Shigeno, M., Saruwatari, Y., Matsui, T.: An algorithm for fractional assignment problems. Discrete Applied Mathematics\u00a056(2\u20133), 333\u2013343 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"33_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10898-004-5119-8","volume":"30","author":"C.C. Skiscim","year":"2004","unstructured":"Skiscim, C.C., Palocsay, S.W.: The complexity of minimum ratio spanning tree problems. Journal of Global Optimization\u00a030, 335\u2013346 (2004)","journal-title":"Journal of Global Optimization"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:23Z","timestamp":1619493563000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11785293_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}