{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T14:07:23Z","timestamp":1774620443169,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319231136","type":"print"},{"value":"9783319231143","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","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":[[2015]]},"DOI":"10.1007\/978-3-319-23114-3_17","type":"book-chapter","created":{"date-parts":[[2015,8,27]],"date-time":"2015-08-27T09:01:33Z","timestamp":1440666093000},"page":"273-287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximation Schemes for Multi-objective Optimization with Quadratic Constraints of Fixed CP-Rank"],"prefix":"10.1007","author":[{"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[]},{"given":"Trung Thanh","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,28]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing $$2+\\epsilon $$ approximation for unsplittable flow on a path. In: SODA, pp. 26\u201341 (2014)","DOI":"10.1137\/1.9781611973402.3"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, A., Chakrabarti, N., Epstein, A., Schieber, B.: A quasi-ptas for unsplittable flow on line graphs. In: STOC, pp. 721\u2013729 (2006)","DOI":"10.1145\/1132516.1132617"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, M.R.: A logarithmic approximation for unsplittable flow on line graphs. In: SODA, pp. 702\u2013709 (2009)","DOI":"10.1137\/1.9781611973068.77"},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4086\/toc.2012.v008a024","volume":"8","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: Solving packing integer programs via randomized rounding with alterations. Theory of Computing 8(1), 533\u2013565 (2012)","journal-title":"Theory of Computing"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. In STOC, pp. 735\u2013744 (2000)","DOI":"10.1145\/335305.335410"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Bartlett, M., Frisch, A.M., Hamadi, Y., Miguel, I., Tarim, S.A., Unsworth, C.: The temporal knapsack problem and its solution. In: Bart\u00e1k, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol. 3524, pp. 34\u201348. Springer, Heidelberg (2005)","DOI":"10.1007\/11493853_5"},{"key":"17_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.jda.2013.06.006","volume":"22","author":"C Bazgan","year":"2013","unstructured":"Bazgan, C., Gourv\u00e8s, L., Monnot, J.: Approximation with a fixed number of solutions of some multiobjective maximization problems. J. Discrete Algorithms 22, 19\u201329 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"17_CR8","unstructured":"Bazgan, C., Gourv\u00e8s, L., Monnot, J., Pascual, F.: Single approximation for the biobjective max TSP. Theor. Comput. Sci. 478, 41\u201350 (2013)"},{"key":"17_CR9","unstructured":"Bazgan, C., Hugot, H., Vanderpooten, D.: Solving efficiently the 0\u20131 multi-objective knapsack problem. Comput. & OR 36(1), 260\u2013279 (2009)"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003)","DOI":"10.1142\/5273"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chakrabarti, A., Karloff, H., Rabani, Y.: Improved approximation algorithms for resource allocation. In: Cook, W.J., Schulz, A.S. (eds.) IPCO 2002. LNCS, vol. 2337, pp. 401\u2013414. Springer, Heidelberg (2002)","DOI":"10.1007\/3-540-47867-1_28"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Chekuri, C., Gupta, A., Kumar, A.: Approximation algorithms for the unsplittable flow problem. Algorithmica 47(1), 53\u201378 (2007)","DOI":"10.1007\/s00453-006-1210-5"},{"key":"17_CR13","unstructured":"Chau, C., Elbassioni, K., Khonji, M.: Truthful mechanisms for combinatorial ac electric power allocation. In: AAMAS, pp. 1005\u20131012 (2014)"},{"key":"17_CR14","unstructured":"Cheng, T., Janiak, A., Kovalyov, M.: Bicriterion single machine scheduling with resource dependent processing times. SIAM J. Optim. 8(2), 617\u2013630 (1998)"},{"key":"17_CR15","unstructured":"Diakonikolas, I.: Approximation of Multiobjective Optimization Problems. PhD thesis, Deptartment of Computer Science, Columbia University, May 2011"},{"key":"17_CR16","unstructured":"Diakonikolas, I., Yannakakis, M.: Small approximate pareto sets for biobjective shortest paths and other problems. SIAM J. Comput. 39(4), 1340\u20131371 (2009)"},{"key":"17_CR17","unstructured":"Dickinson, P., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57(2), 403\u2013415 (2014)"},{"key":"17_CR18","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, Heidelberg (2005)"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Ehrgott, M., Gandibleux, X.: Multiple Criteria Optimization: State of the Art Annotated Bibliographical Surveys. Kluwer, Boston (2002)","DOI":"10.1007\/b101915"},{"key":"17_CR20","unstructured":"Elbassioni, K., Nguyen,T.T.: Approximation schemes for binary quadratic programming problems with low cp-rank decompositions. CoRR (2014). abs\/1411.5050"},{"key":"17_CR21","unstructured":"Erlebach, T., Kellerer, H., Pferschy, U.: Approximating multiobjective knapsack problems. Manage. Sci. 48(12), 1603\u20131612 (2002)"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monnot, J.: Fair solutions for some multiagent optimization problems. Auton. Agent. Multi-Agent Syst. 26(2), 184\u2013201 (2013)","DOI":"10.1007\/s10458-011-9188-z"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Frieze, A., Clarke, M.: Approximation algorithms for the $$m$$-dimensional 0\u20131 knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res. 15, 100\u2013109 (1984)","DOI":"10.1016\/0377-2217(84)90053-5"},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"Gandibleux, X., Freville, A.: Tabu search based procedure for solving the 0\u20131 multiobjective knapsack problem: the two objective case. J. Heuristics 6, 361\u2013383 (2000)","DOI":"10.1023\/A:1009682532542"},{"key":"17_CR25","unstructured":"Grainger, J., Stevenson, W.: Power System Analysis. McGraw-Hill, New York (1994)"},{"key":"17_CR26","unstructured":"Hong, S.-P., Chung, S.-J., Park, B.H.: A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. Oper. Res. Lett. 32(3), 233\u2013239 (2004)"},{"key":"17_CR27","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-24777-7"},{"key":"17_CR28","doi-asserted-by":"crossref","unstructured":"Leonardi, S., Marchetti-Spaccamela, A., Vitaletti, A.: Approximation algorithms for bandwidth and storage allocation problems under real time constraints. In: FSTTCS, pp. 409\u2013420 (2000)","DOI":"10.1007\/3-540-44450-5_33"},{"key":"17_CR29","unstructured":"Mittal, S., Schulz, A.: A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one. Oper. Res. 61(2), 386\u2013397 (2013)"},{"key":"17_CR30","doi-asserted-by":"crossref","unstructured":"Nemirovski, A., Todd, M.: Interior-point methods for optimization. Acta Numerica 17, 191\u2013234 (2008)","DOI":"10.1017\/S0962492906370018"},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: FOCS, pp. 86\u201392 (2000)","DOI":"10.1109\/SFCS.2000.892068"},{"key":"17_CR32","doi-asserted-by":"crossref","unstructured":"Schaible, S., Shi, J.: Fractional programming: the sum-of-ratios case. Optim. Methods Softw. 18, 219\u2013229 (2003)","DOI":"10.1080\/1055678031000105242"},{"key":"17_CR33","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"key":"17_CR34","doi-asserted-by":"crossref","unstructured":"Tsaggouris, G., Zaroliagis, C.D.: Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications. Theory Comput. Syst. 45(1), 162\u2013186 (2009)","DOI":"10.1007\/s00224-007-9096-4"},{"key":"17_CR35","unstructured":"Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of an FPTAS?. In: SODA, pp. 820\u2013829 (1999)"},{"key":"17_CR36","unstructured":"Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12(1), 57\u201374 (2000)"},{"key":"17_CR37","unstructured":"Yu, L., Chau, C.: Complex-demand knapsack problems and incentives in ac power systems. In: AAMAS, pp. 973\u2013980 (2013)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Decision Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23114-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T05:33:18Z","timestamp":1748583198000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-23114-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319231136","9783319231143"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23114-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}