{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T02:12:36Z","timestamp":1712369556352},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,5,8]],"date-time":"2010-05-08T00:00:00Z","timestamp":1273276800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2010,7]]},"DOI":"10.1007\/s10107-010-0364-8","type":"journal-article","created":{"date-parts":[[2010,5,6]],"date-time":"2010-05-06T22:05:00Z","timestamp":1273183500000},"page":"255-269","source":"Crossref","is-referenced-by-count":10,"title":["Approximating a class of combinatorial problems with rational objective function"],"prefix":"10.1007","volume":"124","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","published-online":{"date-parts":[[2010,5,8]]},"reference":[{"issue":"5","key":"364_CR1","doi-asserted-by":"crossref","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. Oper. Res. Lett. 30(5), 336\u2013342 (2002)","journal-title":"Oper. Res. Lett."},{"key":"364_CR2","doi-asserted-by":"crossref","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. Oper. Res. 24, 675\u2013699 (1976)","journal-title":"Oper. Res."},{"key":"364_CR3","doi-asserted-by":"crossref","unstructured":"Carlson, J., Eppstein, D.: The weighted maximum-mean subtree and other bicriterion subtree problems. In: ACM Computing Research Repository, cs.CG\/0503023. (2005)","DOI":"10.1007\/11785293_37"},{"key":"364_CR4","doi-asserted-by":"crossref","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. J. Comb. Optim. 9, 69\u201390 (2005)","journal-title":"J. Comb. Optim."},{"key":"364_CR5","first-page":"77","volume-title":"Theory of Graphs: International Symposium","author":"G.B. Dantzig","year":"1967","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. (eds) Theory of Graphs: International Symposium, pp. 77\u201384. Dunod, Paris (1967)"},{"issue":"10","key":"364_CR6","doi-asserted-by":"crossref","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 Trans. Comp. Aid. Des. Integr. Circ. Syst. 17(10), 889\u2013899 (1998)","journal-title":"IEEE Trans. Comp. Aid. Des. Integr. Circ. Syst."},{"key":"364_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":"364_CR8","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1287\/mnsc.13.7.492","volume":"13","author":"W. Dinkelbach","year":"1967","unstructured":"Dinkelbach W.: On nonlinear fractional programming. Manag. Sci. 13, 492\u2013498 (1967)","journal-title":"Manag. Sci."},{"key":"364_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2014Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP\u2014Completeness. W.H. Freeman and Co., New York (1979)"},{"key":"364_CR10","doi-asserted-by":"crossref","unstructured":"Gubbala, P., Raghavachari, B.: Finding k\u2014connected subgraphs with minimum average weight. In: Proceedings of the 6th Latin American Theoretical Informatics Symposium (LATIN), Lecture Notes in Computer Science, vol. 2976, pp. 212\u2013221. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24698-5_25"},{"key":"364_CR11","doi-asserted-by":"crossref","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. Math. Program. 37, 255\u2013267 (1987)","journal-title":"Math. Program."},{"key":"364_CR12","doi-asserted-by":"crossref","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. Manag. Sci. 12, 609\u2013615 (1966)","journal-title":"Manag. Sci."},{"issue":"1","key":"364_CR13","doi-asserted-by":"crossref","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 21(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"issue":"1","key":"364_CR14","doi-asserted-by":"crossref","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. J. Algorithms 45(1), 1\u201315 (2002)","journal-title":"J. Algorithms"},{"issue":"3","key":"364_CR15","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"R.M. Karp","year":"1978","unstructured":"Karp R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23(3), 309\u2013311 (1978)","journal-title":"Discrete Math."},{"issue":"2","key":"364_CR16","doi-asserted-by":"crossref","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 Appl. Math. 35(2), 143\u2013155 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"364_CR17","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. J. Assoc. Comput. Mach. 41(2), 214\u2013235 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"key":"364_CR18","doi-asserted-by":"crossref","unstructured":"Klau, G., Ljubi, I. Mutzel, P. Pferschy, U., Weiskircher R.: The fractional prize collecting Steiner tree problem on trees. In: Proceedings of the 11th European Symposium on Algorithms (ESA 2003), Lecture Notes in Computer Science, vol. 2832, pp. 691\u2013702. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-39658-1_62"},{"key":"364_CR19","first-page":"209","volume-title":"Theory of Graphs: International Symposium","author":"E.L. Lawler","year":"1967","unstructured":"Lawler E.L.: Optimal cycles in doubly weighted directed linear graphs. In: Rosensthiel, P. (eds) Theory of Graphs: International Symposium, pp. 209\u2013214. Dunod, Paris (1967)"},{"issue":"4","key":"364_CR20","doi-asserted-by":"crossref","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. Math. Oper. Res. 4(4), 414\u2013424 (1979)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"364_CR21","doi-asserted-by":"crossref","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. Math. Program. 54(1), 41\u201356 (1992)","journal-title":"Math. Program."},{"key":"364_CR22","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou C.H., Yannakakis M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci 43, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci"},{"key":"364_CR23","doi-asserted-by":"crossref","unstructured":"Radzik T. Newton\u2019s method for fractional combinatorial optimization. In: Proceeings of 33rd Annual Symposium on Foundations of Computer Science, pp. 659\u2013669 (1992)","DOI":"10.1109\/SFCS.1992.267785"},{"issue":"2\u20133","key":"364_CR24","doi-asserted-by":"crossref","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 Appl. Math. 56(2\u20133), 333\u2013343 (1995)","journal-title":"Discrete Appl. Math."},{"key":"364_CR25","doi-asserted-by":"crossref","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. J. Glob. Optim. 30, 335\u2013346 (2004)","journal-title":"J. Glob. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0364-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-010-0364-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0364-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T05:50:08Z","timestamp":1559109008000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-010-0364-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,8]]},"references-count":25,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["364"],"URL":"https:\/\/doi.org\/10.1007\/s10107-010-0364-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,8]]}}}