Article ID: | iaor20061419 |
Country: | United States |
Volume: | 30 |
Issue: | 4 |
Start Page Number: | 880 |
End Page Number: | 896 |
Publication Date: | Nov 2005 |
Journal: | Mathematics of Operations Research |
Authors: | Hassin Refael, Einstein Ori |
This paper deals with families of optimization problems defined over a common set of potential solutions. We consider several problems–solutions systems, and for each one, prove the existence of a small set of solutions that contains an optimal solution to every problem. These proofs are mostly algebraic in nature. The families of problems covered here mostly include separation problems, problems on graphs and hypergraphs, and SAT problems.