{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T17:23:52Z","timestamp":1774373032567,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,2,1]],"date-time":"2005-02-01T00:00:00Z","timestamp":1107216000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2005,2]]},"DOI":"10.1007\/s10878-005-5485-2","type":"journal-article","created":{"date-parts":[[2005,2,16]],"date-time":"2005-02-16T22:08:53Z","timestamp":1108591733000},"page":"69-90","source":"Crossref","is-referenced-by-count":20,"title":["Efficient Algorithms and Implementations for Optimizing the Sum of Linear Fractional Functions, with Applications"],"prefix":"10.1007","volume":"9","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[]},{"given":"Ovidiu","family":"Daescu","sequence":"additional","affiliation":[]},{"given":"Yang","family":"Dai","sequence":"additional","affiliation":[]},{"given":"Naoki","family":"Katoh","sequence":"additional","affiliation":[]},{"given":"Xiaodong","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/PL00009204","volume":"21","author":"E.M. Arkin","year":"1998","unstructured":"E.M. Arkin, Y.-J. Chiang, M. Held, J.S.B. Mitchell, V. Sacristan, S.S. Skiena, and T.-C. Yang ?On minimum-area hulls,? Algorithmica, vol. 21, pp. 119?136, 1998.","journal-title":"Algorithmica"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"A.I. Barros Discrete and Fractional Programming Techniques for Location Models, North Holland, 1998.","DOI":"10.1007\/978-1-4615-4072-4"},{"key":"CR3","unstructured":"D.A. Bini and G. Fiorentino ?Numerical computation of polynomial roots: MPSolve-version 2.0,? FRISCO Report, 1998."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1287\/opre.24.4.675","volume":"24","author":"G.R. Bitran","year":"1976","unstructured":"G.R. Bitran and T.L. Magnanti ?Duality and sensitivity analysis for fractional programs,? OperationsResearch, vol. 24, pp. 675?699, 1976.","journal-title":"Operations Research"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1006\/jagm.1997.0914","volume":"27","author":"T.M. Chan","year":"1998","unstructured":"T.M. Chan ?Deterministic algorithms for 2-d convexprogramming and 3-d online linear programming,? Journal of Algorithms, vol. 27, pp. 147?166, 1998.","journal-title":"Journal of Algorithms"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/net.3230070405","volume":"7","author":"R. Chandrasekaran","year":"1977","unstructured":"R. Chandrasekaran ?Minimum ratio spanning trees,?Networks, vol. 7, pp. 335?342, 1977.","journal-title":"Networks"},{"issue":"4","key":"CR7","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/TIT.1985.1057060","volume":"31","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle ?On the convex layers of a planar set,? IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 509?517, 1985.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"CR8","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1023\/A:1009885517653","volume":"5","author":"D.Z. Chen","year":"2001","unstructured":"D.Z. Chen, O. Daescu, X. Hu, X. Wu, and J. Xu ?Determining an optimal penetration among weighted regions in two and three dimensions,? Journal of Combinatorial Optimization, for a Special Issue on Optimization Problems in Medical Applications, vol. 5, no. 1, pp. 59?79, 2001.","journal-title":"Journal of Combinatorial Optimization, for a Special Issue onOptimization Problems in Medical Applications"},{"key":"CR9","unstructured":"L. Craig, J.L. Zhou, and A.L. Tits ?User?s guide for CFSQP Version 2.5,? Electrical Eng. Dept. and Institute for Systems Research, University of Maryland, TR-94-16r1, 1994."},{"key":"CR10","unstructured":"K. Daniels ?The restrict\/evaluate\/subdivide paradigm for translational containment,? in Proceedings of the Fifth MSI Stony Brook Workshop on Computational Geometry,1995."},{"key":"CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner Algorithms in Combinatorial Geometry, Springer-Verlag: New York, 1987."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H. Edelsbrunner","year":"1989","unstructured":"H. Edelsbrunner and L.J. Guibas ?Topologically sweeping an arrangement,? Journal of Computer and System Sciences, vol. 38, pp. 165?194, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"D. Eppstein ?Dynamic three-dimensional linear programming,? in Proceedings of 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 488?494.","DOI":"10.1109\/SFCS.1991.185410"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"J.E. Falk and S.W. Palocsay ?Optimizing the sum oflinear fractional functions,? in Collection: Recent Advances in Global Optimization, C.A. Floudas and P.M. Pardalos (Eds.), 1992, pp. 221?258.","DOI":"10.1515\/9781400862528.221"},{"issue":"1","key":"CR15","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1023\/A:1008316327038","volume":"19","author":"R.W. Freund","year":"2001","unstructured":"R.W. Freund and F. Jarre ?Solving the sum-of-ratios problem by an interior-point method,? Journal of Global Optimization, vol. 19, no. 1, pp. 83?102, 2001.","journal-title":"Journal of Global Optimization"},{"key":"CR16","unstructured":"L. Ingber Adaptive Simulated Annealing, Optimization Algorithm for Nonlinear and Stochastic Systems, http:\/\/www.ingber.com\/#ASA-CODE."},{"key":"CR17","unstructured":"M. Jelasity and J. Dombi GAS Genetic Algorithm, ftp:\/\/ftp.jate.u-szeged.hu\/pub\/math\/optimization\/GAS\/."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01096534","volume":"4","author":"H. Konno","year":"1994","unstructured":"H. Konno, T. Kuno, and Y. Yajima ?Global minimization of a generalized convex multiplicative function,? Journal of Global Optimization, vol. 4, pp. 47?62, 1994.","journal-title":"Journal of Global Optimization"},{"issue":"3","key":"CR19","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539796305365","volume":"28","author":"G. Liotta","year":"1999","unstructured":"G. Liotta, F.P. Preparata, and R. Tamassia ?Robust proximity queries: An illustration of degree-driven algorithm design,? SIAM Journal on Computing, vol. 28, no. 3, pp. 864?889, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"CR20","unstructured":"J. Majhi, R. Janardan, J. Schwerdt, M. Smid, and P. Gupta ?Minimizing support structures and trapped area in two-dimensional layered manufacturing,? Technical Report TR-97-058, Dept. of Computer Science, University of Minnesota, Dec. 1997a."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"J. Majhi, R. Janardan, M. Smid, and P. Gupta ?On some geometric optimization problems in layered manufacturing,? in Proceedings of the 5th Workshop on Algorithms and Data Structures, vol. 1272, Springer-Verlag, 1997b, pp. 136?149.","DOI":"10.1007\/3-540-63307-3_54"},{"issue":"4","key":"CR22","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/moor.4.4.414","volume":"4","author":"N. Megiddo","year":"1979","unstructured":"N. Megiddo ?Combinatorial optimization with rational objective functions,? Mathematics of Operations Research, vol. 4, no. 4, pp. 414?424, 1979.","journal-title":"Mathematics of Operations Research"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"N. Megiddo ?Linear programming in linear time when the dimension is fixed,? Journal of ACM, vol. 31, pp. 114?127, 1984.","journal-title":"Journal of ACM"},{"key":"CR24","unstructured":"V. Milenkovic, K. Daniels, and Z. Li ?Placement and compaction of nonconvex polygons for clothing manufacture,? in Proceedings of the 4th Canad. Conf. Comput. Geom., 1992, pp. 236?243."},{"key":"CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos Computational Geometry: An Introduction, Springer-Verlag: New York, 1985."},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"T. Radzik ?Newton?s method for fractional combinatorial optimization,? in Proceedings of 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 659?669.","DOI":"10.1109\/SFCS.1992.267785"},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"S. Schaible ?Fractional programming,? in Handbook of Global Optimization, R. Horst and P.M. Pardalos (Eds.), Kluwer Academic Publishers, 1995, pp. 495?608.","DOI":"10.1007\/978-1-4615-2025-2"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1023\/A:1008340311108","volume":"19","author":"C.C. Skiscim","year":"2001","unstructured":"C.C. Skiscim and S. Palocsay ?Minimum spanning trees with sums of ratios,? Journal of Global Optimization, vol. 19, pp. 103?120, 2001.","journal-title":"Journal of Global Optimization"},{"key":"CR29","unstructured":"H. Yamashita ?Efficient algorithms for minimizing the sum and the product of linear fractional functions,? Master Thesis, Dept. of Industrial Engineering and Management, Tokyo Institute of Technology, 1997."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-5485-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-005-5485-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-5485-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T10:44:31Z","timestamp":1734950671000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-005-5485-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,2]]}},"alternative-id":["5485"],"URL":"https:\/\/doi.org\/10.1007\/s10878-005-5485-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,2]]}}}