Presentations at an Academic or Professional conference
Year
2000
Abstract
We focus on how the logical definability of NP-hard optimization problems can help to decide their approximability. Particularly, we deal with NP-hard minimization covering and partitioning problems. We extend some results of Kolaïtis and Thakur by defining a class containing some natural weighted problems whose approximability is an open problem. We show that all problems in this class amount to a generalization of the classical Set Covering problem, called Bi-Set Covering. Examples of such problems concern optimal location and network design.
ALFANDARI, L. (2000). Logical Definability of Covering and Partitioning Minimization Problems. Dans: CLAIO X (Congresso Latino-Americano de Investigacion Operativa)-Latin-American Congress of Operations Research, Mexico.