Skip to main content
Springer Nature Link
Log in

Obtaining Approximately Optimal and Diverse Solutions via Dispersion

  • Conference paper
  • First Online:
LATIN 2022: Theoretical Informatics (LATIN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13568))

Included in the following conference series:

  • 939 Accesses

  • 3 Citations

Abstract

There has been a long-standing interest in computing diverse solutions to optimization problems. In 1995 J. Krarup [28] posed the problem of finding k-edge disjoint Hamiltonian Circuits of minimum total weight, called the peripatetic salesman problem (PSP). Since then researchers have investigated the complexity of finding diverse solutions to spanning trees, paths, vertex covers, matchings, and more. Unlike the PSP that has a constraint on the total weight of the solutions, recent work has involved finding diverse solutions that are all optimal.

However, sometimes the space of exact solutions may be too small to achieve sufficient diversity. Motivated by this, we initiate the study of obtaining sufficiently-diverse, yet approximately-optimal solutions to optimization problems. Formally, given an integer k, an approximation factor c, and an instance I of an optimization problem, we aim to obtain a set of k solutions to I that a) are all c approximately-optimal for I and b) maximize the diversity of the k solutions. Finding such solutions, therefore, requires a better understanding of the global landscape of the optimization function.

Given a metric on the space of solutions, and the diversity measure as the sum of pairwise distances between solutions, we first provide a general reduction to an associated budget-constrained optimization (BCO) problem, where one objective function is to optimized subject to a bound on the second objective function. We then prove that bi-approximations to the BCO can be used to give bi-approximations to the diverse approximately optimal solutions problem.

As applications of our result, we present polynomial time approximation algorithms for several problems such as diverse c-approximate maximum matchings, \(s-t\) shortest paths, global min-cut, and minimum weight bases of a matroid. The last result gives us diverse c-approximate minimum spanning trees, advancing a step towards achieving diverse c-approximate TSP tours.

We also explore the connection to the field of multiobjective optimization and show that the class of problems to which our result applies includes those for which the associated DUALRESTRICT problem defined by Papadimitriou and Yannakakis [35], and recently explored by Herzel et al. [26] can be solved in polynomial time.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 74.89
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 96.29
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We assume without loss of generality that the optimal TSP is combinatorially unique by a slight perturbation of the distances.

  2. 2.

    While an exact algorithm for diverse unweighted spanning trees is known [23], we give a faster (by a factor \(\varOmega (n^{1.5}k^{1.5}/\alpha (n, m))\) where \(\alpha (\cdot )\) denotes the inverse of the Ackermann function), 2-approximation here.

  3. 3.

    We define the measure function only for feasible solutions of an instance. Indeed if an algorithm solving the optimization problem outputs a non-feasible solution, then the measure just evaluates to -1 in case of maximization problems and \(\infty \) in case of minimization problems.

  4. 4.

    The latter is a PTAS, not an FPTAS.

References

  1. Abbar, S., Amer-Yahia, S., Indyk, P., Mahabadi, S., Varadarajan, K.R.: Diverse near neighbor problem. In: Symposium on Computational Geometry (SoCG), pp. 207–214. ACM (2013)

    Google Scholar 

  2. Armon, A., Zwick, U.: Multicriteria global minimum cuts. Algorithmica 46(1), 15–26 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ausiello, G., Marchetti-Spaccamela, A., Crescenzi, P., Gambosi, G., Protasi, M., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (1999). https://doi.org/10.5555/554706

    Book  MATH  Google Scholar 

  4. Baste, J., et al.: Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory. Artif. Intell. 303, 103644 (2022)

    Google Scholar 

  5. Baste, J., Jaffke, L., Masařík, T., Philip, G., Rote, G.: FPT algorithms for diverse collections of hitting sets. Algorithms 12(12), 254 (2019)

    Article  MathSciNet  Google Scholar 

  6. Berger, A., Bonifaci, V., Grandoni, F., Schäfer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. Math. Program. 128(1–2), 355–372 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Birnbaum, B.E., Goldman, K.J.: An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs. Algorithmica 55(1), 42–59 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Borodin, A., Jain, A., Lee, H.C., Ye, Y.: Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Trans. Algorithms 13(3), 41:1–41:25 (2017)

    Google Scholar 

  9. Camerini, P.M., Galbiati, G., Maffioli, F.: Random pseudo-polynomial algorithms for exact matroid problems. J. Algorithms 13(2), 258–273 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cevallos, A., Eisenbrand, F., Zenklusen, R.: Max-sum diversity via convex programming. In: Fekete, S.P., Lubiw, A. (eds.) 32nd International Symposium on Computational Geometry, SoCG 2016, 14–18 June 2016, Boston, MA, USA. LIPIcs, vol. 51, pp. 26:1–26:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

    Google Scholar 

  11. Cevallos, A., Eisenbrand, F., Zenklusen, R.: Local search for max-sum diversification. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 130–142. SIAM (2017)

    Google Scholar 

  12. Clausen, J., Hansen, L.A.: Finding k edge-disjoint spanning trees of minimum total weight in a network: an application of matroid theory. In: Rayward-Smith, V.J. (ed.) Combinatorial Optimization II. Mathematical Programming Studies, vol. 13, pp. 88–101. Springer, Heidelberg (1980). https://doi.org/10.1007/BFb0120910

    Chapter  Google Scholar 

  13. Commander, C.W., Pardalos, P.M., Ryabchenko, V., Uryasev, S., Zrazhevsky, G.: The wireless network jamming problem. J. Comb. Optim. 14(4), 481–498 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  14. Diakonikolas, I., Yannakakis, M.: Small approximate pareto sets for biobjective shortest paths and other problems. SIAM J. Comput. 39(4), 1340–1371 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  15. Erkut, E.: The discrete P-dispersion problem. Eur. J. Oper. Res. 46(1), 48–60 (1990). https://doi.org/10.1016/0377-2217(90)90297-O, https://www.sciencedirect.com/science/article/pii/037722179090297O

  16. Fomin, F.V., Golovach, P.A., Jaffke, L., Philip, G., Sagunov, D.: Diverse pairs of matchings. In: 31st International Symposium on Algorithms and Computation (ISAAC). LIPIcs, vol. 181, pp. 26:1–26:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  17. Fomin, F.V., Golovach, P.A., Panolan, F., Philip, G., Saurabh, S.: Diverse collections in matroids and graphs. In: Bläser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, 16–19 March 2021, Saarbrücken, Germany (Virtual Conference). LIPIcs, vol. 187, pp. 31:1–31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

    Google Scholar 

  18. Gabow, H.N.: Two algorithms for generating weighted spanning trees in order. SIAM J. Comput. 6(1), 139–150 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  19. Gao, J., Goswami, M., Karthik, C.S., Tsai, M.T., Tsai, S.Y., Yang, H.T.: Obtaining approximately optimal and diverse solutions via dispersion (2022). https://doi.org/10.48550/ARXIV.2202.10028, https://arxiv.org/abs/2202.10028

  20. Goldenberg, E., Karthik C. S.: Hardness amplification of optimization problems. In: Vidick, T. (ed.) 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, 12–14 January 2020, Seattle, Washington, USA. LIPIcs, vol. 151, pp. 1:1–1:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.1

  21. Hanaka, T., Kiyomi, M., Kobayashi, Y., Kobayashi, Y., Kurita, K., Otachi, Y.: A framework to design approximation algorithms for finding diverse solutions in combinatorial problems. CoRR abs/2201.08940 (2022)

    Google Scholar 

  22. Hanaka, T., Kobayashi, Y., Kurita, K., Lee, S.W., Otachi, Y.: Computing diverse shortest paths efficiently: a theoretical and experimental study. CoRR abs/2112.05403 (2021)

    Google Scholar 

  23. Hanaka, T., Kobayashi, Y., Kurita, K., Otachi, Y.: Finding diverse trees, paths, and more. In: Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI), pp. 3778–3786. AAAI Press (2021)

    Google Scholar 

  24. Hara, S., Maehara, T.: Enumerate lasso solutions for feature selection. In: Singh, S.P., Markovitch, S. (eds.) Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI), pp. 1985–1991. AAAI Press (2017)

    Google Scholar 

  25. Hassin, R., Rubinstein, S., Tamir, A.: Approximation algorithms for maximum dispersion. Oper. Res. Lett. 21(3), 133–137 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  26. Herzel, A., Bazgan, C., Ruzika, S., Thielen, C., Vanderpooten, D.: One-exact approximate pareto sets. J. Global Optim. 80(1), 87–115 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  27. Herzel, A., Ruzika, S., Thielen, C.: Approximation methods for multiobjective optimization problems: a survey. INFORMS J. Comput. 33(4), 1284–1299 (2021)

    MathSciNet  MATH  Google Scholar 

  28. Krarup, J.: The peripatetic salesman and some related unsolved problems. In: Roy, B. (ed.) Combinatorial Programming: Methods and Applications. NATO Advanced Study Institutes Series, vol. 19, pp. 173–178. Springer, Dordrecht (1995). https://doi.org/10.1007/978-94-011-7557-9_8

    Chapter  Google Scholar 

  29. Kuby, M.: Programming models for facility dispersion: the P-dispersion and maxisum dispersion problems. Geogr. Anal. 19(4), 315–329 (1987). https://doi.org/10.1111/j.1538-4632.1987.tb00133.x

    Article  Google Scholar 

  30. Lawler, E.L.: A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Manage. Sci. 18(7), 401–405 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  31. Lindgren, E.M., Dimakis, A.G., Klivans, A.: Exact map inference by avoiding fractional vertices. In: International Conference on Machine Learning, pp. 2120–2129. PMLR (2017)

    Google Scholar 

  32. Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Comb. 7(1), 105–113 (1987)

    MathSciNet  MATH  Google Scholar 

  33. Murty, K.G.: An algorithm for ranking all the assignments in order of increasing cost. Oper. Res. 16(3), 682–687 (1968)

    Article  MATH  Google Scholar 

  34. Namorado Climaco, J.C., Queirós Vieira Martins, E.: A bicriterion shortest path algorithm. Eur. J. Oper. Res. 11(4), 399–404 (1982)

    Google Scholar 

  35. Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 86–92. IEEE (2000)

    Google Scholar 

  36. Ravi, R., Goemans, M.X.: The constrained minimum spanning tree problem. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 66–75. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61422-2_121

    Chapter  Google Scholar 

  37. Ravi, S.S., Rosenkrantz, D.J., Tayi, G.K.: Heuristic and special case algorithms for dispersion problems. Oper. Res. 42(2), 299–310 (1994)

    Article  MATH  Google Scholar 

  38. Wang, D., Kuo, Y.S.: A study on two geometric location problems. Inf. Process. Lett. 28(6), 281–286 (1988) https://doi.org/10.1016/0020-0190(88)90174-3, https://www.sciencedirect.com/science/article/pii/0020019088901743

  39. Yang, H.T., Tsai, S.Y., Liu, K.S., Lin, S., Gao, J.: Patrol scheduling against adversaries with varying attack durations. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1179–1188 (2019)

    Google Scholar 

Download references

Acknowledgements

Mayank Goswami would like to acknowledge support from the National Science Foundation grants CRII-1755791 and CCF-1910873. Jie Gao would like to acknowledge support OAC-1939459, CCF-2118953 and CCF-2208663. Karthik C. S. would like to acknowledge support from Rutgers University’s Research Council Individual Fulcrum Award (#AWD00010234) and a grant from the Simons Foundation, Grant Number 825876, Awardee Thu D. Nguyen. Meng-Tsung Tsai would like to acknowledge support from the Ministry of Science and Technology of Taiwan grant 109-2221-E-001-025-MY3.

Author information

Authors and Affiliations

  1. Department of Computer Science, Rutgers University, New Brunswick, USA

    Jie Gao & C. S. Karthik

  2. Department of Computer Science, Queens College, City University of New York, New York, USA

    Mayank Goswami

  3. Institute of Information Science, Academia Sinica, Taipei, Taiwan

    Meng-Tsung Tsai

  4. Department of Computer Science, Stony Brook University, Stony Brook, USA

    Shih-Yu Tsai

  5. Department of Computer Science and Information Engineering, National Central University, Taoyuan, Taiwan

    Hao-Tsung Yang

Authors
  1. Jie Gao
    View author publications

    Search author on:PubMed Google Scholar

  2. Mayank Goswami
    View author publications

    Search author on:PubMed Google Scholar

  3. C. S. Karthik
    View author publications

    Search author on:PubMed Google Scholar

  4. Meng-Tsung Tsai
    View author publications

    Search author on:PubMed Google Scholar

  5. Shih-Yu Tsai
    View author publications

    Search author on:PubMed Google Scholar

  6. Hao-Tsung Yang
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Mayank Goswami .

Editor information

Editors and Affiliations

  1. Universidad Nacional Autónoma de México, Mexico City, Mexico

    Armando Castañeda

  2. Centro de investigación y de Estudios Avanzados, Mexico City, Mexico

    Francisco Rodríguez-Henríquez

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Gao, J., Goswami, M., Karthik, C.S., Tsai, MT., Tsai, SY., Yang, HT. (2022). Obtaining Approximately Optimal and Diverse Solutions via Dispersion. In: Castañeda, A., Rodríguez-Henríquez, F. (eds) LATIN 2022: Theoretical Informatics. LATIN 2022. Lecture Notes in Computer Science, vol 13568. Springer, Cham. https://doi.org/10.1007/978-3-031-20624-5_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-20624-5_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-20623-8

  • Online ISBN: 978-3-031-20624-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics