This research addresses an important set of questions arising in optimization of industrial systems for network design, data classification, facility location, and scheduling. A fundamental problem arising in all these areas is called set covering. Set covering problems range from easy to very difficult and it is the more difficult ones that form the focus of this research. The problems studied are approached through rigorous and mathematical methods.
This research studies several approaches to the design of algorithms for set covering problems arising in the areas of network design, facility location and data classification, mostly based on mathematical programming techniques. The focus is on the study of complexity and approximability of set covering and its extensions in network design and classification, including the design of general algorithmic techniques and the analysis of mathematical programming formulations and relaxations. A special emphasis is made on set covering problems defined on directed graphs, which is an area where very few results are available in the literature.
