The number of solutions sufficient for solving a family of problems

• 成果类型: Article
• 署名作者: Einstein, O; Hassin, R
• 署名单位: Tel Aviv University; Tel Aviv University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0161
• 发表日期: 2005
• 页码: 880-896
• 关键词: incidence matrices; rank; subsets

摘要

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.