The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment

Erick Moreno-Centeno () and Richard M. Karp ()
Additional contact information
Erick Moreno-Centeno: Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843
Richard M. Karp: Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, California 94720; and International Computer Science Institute, Berkeley, California 94704

Operations Research, 2013, vol. 61, issue 2, 453-468

Abstract: We develop a novel framework, the implicit hitting set approach , for solving a class of combinatorial optimization problems. The explicit hitting set problem is as follows: given a set U and a family S of subsets of U , find a minimum-cardinality set that intersects (hits) every set in S . In the implicit hitting set problem (IHSP), the family of subsets S is not explicitly listed (its size is, generally, exponential in terms of the size of U ); instead, it is given via a polynomial-time oracle that verifies if a given set H is a hitting set or returns a set in S that is not hit by H . Many NP-hard problems can be straightforwardly formulated as implicit hitting set problems. We show that the implicit hitting set approach is valuable in developing exact and heuristic algorithms for solving this class of combinatorial optimization problems. Specifically, we provide a generic algorithmic strategy, which combines efficient heuristics and exact methods, to solve any IHSP. Given an instance of an IHSP, the proposed algorithmic strategy gives a sequence of feasible solutions and lower bounds on the optimal solution value and ultimately yields an optimal solution. We specialize this algorithmic strategy to solve the multigenome alignment problem and present computational results that illustrate the effectiveness of the implicit hitting set approach.

Keywords: combinatorial optimization; exact algorithms; heuristic algorithms; multigenome alignment problem; multisequence alignment problem (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1139 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:2:p:453-468

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().