{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:46:16Z","timestamp":1760233576203,"version":"build-2065373602"},"reference-count":16,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T00:00:00Z","timestamp":1612224000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Disjoint Connecting Paths problem and its capacitated generalization, called Unsplittable Flow problem, play an important role in practical applications such as communication network design and routing. These tasks are NP-hard in general, but various polynomial-time approximations are known. Nevertheless, the approximations tend to be either too loose (allowing large deviation from the optimum), or too complicated, often rendering them impractical in large, complex networks. Therefore, our goal is to present a solution that provides a relatively simple, efficient algorithm for the unsplittable flow problem in large directed graphs, where the task is NP-hard, and is known to remain NP-hard even to approximate up to a large factor. The efficiency of our algorithm is achieved by sacrificing a small part of the solution space. This also represents a novel paradigm for approximation. Rather than giving up the search for an exact solution, we restrict the solution space to a subset that is the most important for applications, and excludes only a small part that is marginal in some well-defined sense. Specifically, the sacrificed part only contains scenarios where some edges are very close to saturation. Since nearly saturated links are undesirable in practical applications, therefore, excluding near saturation is quite reasonable from the practical point of view. We refer the solutions that contain no nearly saturated edges as safe solutions, and call the approach safe approximation. We prove that this safe approximation can be carried out efficiently. That is, once we restrict ourselves to safe solutions, we can find the exact optimum by a randomized polynomial time algorithm.<\/jats:p>","DOI":"10.3390\/a14020048","type":"journal-article","created":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T13:01:12Z","timestamp":1612270872000},"page":"48","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Safe Approximation\u2014An Efficient Solution for a Hard Routing Problem"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8952-6946","authenticated-orcid":false,"given":"Andr\u00e1s","family":"Farag\u00f3","sequence":"first","affiliation":[{"name":"Department of Computer Science, Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas, P.O.B. 830688, MS-EC31, Richardson, TX 75080, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2170-8318","authenticated-orcid":false,"given":"Zohre R.","family":"Mojaveri","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas, P.O.B. 830688, MS-EC31, Richardson, TX 75080, USA"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Miller, R.E., and Thatcher, J.W. (1972). Reducibility Among Combinatorial Problems. Complexity of Computer Computations, Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_2","unstructured":"Preparata, F. (1984). The Complexity of Wire Routing and Finding the Minimum Area Layouts for Arbitrary VLSI Circuits. Advances in Computing Research 2: VLSI Theory, JAI Press."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Cook, W., and Seymour, P.D. (1990). On the Complexity of the Disjoint Paths Problem. Polyhedral Combinatorics, American Mathematical Society. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.","DOI":"10.1090\/dimacs\/001"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Garg, N., Vazirani, V., and Yannakakis, M. (1993). Primal-Dual Approximation Algorithms for Integral Flow and Multicuts in Trees, with Applications to Matching and Set Cover. International Colloquium on Automata, Languages, and Programming, Springer.","DOI":"10.1007\/3-540-56939-1_62"},{"key":"ref_5","unstructured":"Farag\u00f3, A. (1985). Algorithmic Problems in Graph Theory. Conference of Program Designers, E\u00f6tv\u00f6s Lor\u00e1nd University of Sciences."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Broder, A.A., Frieze, A.M., Suen, S., and Upfal, E. (1994, January 23\u201325). Optimal Construction of Edge-Disjoint Paths in Random Graphs. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, VA, USA.","DOI":"10.1137\/S0097539792232021"},{"key":"ref_7","first-page":"65","article-title":"Graph Minors-XIII: The Disjoint Paths Problem","volume":"63","author":"Robertson","year":"1995","journal-title":"J. Comb."},{"key":"ref_8","unstructured":"Ball, M.O., Magnanti, T.L., Monma, C.L., and Nemhauser, G.L. (1995). Algorithmic implications of the Graph Minor Theorem. Handbook in Operations Research and Management Science 7: Network Models, North-Hollandhl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","article-title":"On the complexity of timetable and multicommodity flow problems","volume":"5","author":"Even","year":"1976","journal-title":"SIAM J. Comput."},{"key":"ref_10","unstructured":"Aumann, Y., and Rabani, Y. (1995, January 22\u201324). Improved Bounds for All-Optical Routing. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, CA, USA."},{"key":"ref_11","unstructured":"Kleinberg, J., and Tardos, \u00c9. (June, January 29). Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks. Proceedings of the ACM Symposium on Theory of Computing (STOC\u201995), Las Vegas, NV, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","article-title":"Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems","volume":"67","author":"Guruswami","year":"2003","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_13","unstructured":"Srinivasan, A. (1997, January 19\u201322). Improved Approximations for Edge-disjoint Paths, Unsplittable Flow, and Related Routing Problems. Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS\u201997), Miami Beach, FL, USA."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.jalgor.2004.07.006","article-title":"Improved Bounds for the Unsplittable Flow Problem","volume":"61","author":"Kolman","year":"2006","journal-title":"J. Algorithms"},{"key":"ref_15","unstructured":"Gonzales, T. (2020). Handbook of Approximation Algorithms and Metaheuristics, Chapman and Hall\/CRC."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","article-title":"Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs","volume":"37","author":"Raghavan","year":"1988","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/48\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:18:44Z","timestamp":1760159924000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,2]]},"references-count":16,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["a14020048"],"URL":"https:\/\/doi.org\/10.3390\/a14020048","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,2,2]]}}}