Obtaining Approximately Optimal and Diverse Solutions via Dispersion

Jie Gao, Mayank Goswami, C. S. Karthik, Meng Tsung Tsai, Shih Yu Tsai, Hao Tsung Yang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations


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.

Original languageEnglish
Title of host publicationLATIN 2022
Subtitle of host publicationTheoretical Informatics - 15th Latin American Symposium, 2022, Proceedings
EditorsArmando Castañeda, Francisco Rodríguez-Henríquez, Francisco Rodríguez-Henríquez
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages18
ISBN (Print)9783031206238
StatePublished - 2022
Event15th Latin American Symposium on Theoretical Informatics, LATIN 2022 - Guanajuato, Mexico
Duration: 7 Nov 202211 Nov 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13568 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th Latin American Symposium on Theoretical Informatics, LATIN 2022


  • Dispersion problem
  • Diversity
  • Maximum matching
  • Minimum spanning tree
  • Shortest path
  • Travelling salesman problem


Dive into the research topics of 'Obtaining Approximately Optimal and Diverse Solutions via Dispersion'. Together they form a unique fingerprint.

Cite this