| The motivation of this thesis is twofold: (i) designing approximation algorithms for NP-hard covering problems in graphs by unearthing polyhedral roots to better understood problems, and (ii) a dual approach in which we hope to expand the foundation of well-understood polyhedra.; Our design of approximation algorithms focuses on the Edge-dominating Set Problem, that of covering the edges of an edge-weighted graph, ( V, E), with its edges at minimum cost. This problem captures the notion of covering in graphs in the sense that it is a common generalization of the well-studied Vertex Cover (cover E using V) and Edge Cover (cover V using E) problems and can be used to model a specialization of the Total Cover Problem (cover V ∪ E using V ∪ E). To the best of our knowledge, we present among the first nontrivial approximation algorithms for this problem, culminating with a 2-approximation. This is tight in the sense that it matches the approximability of its specialization, Vertex Cover, which has eluded a constant-factor improvement in approximability for decades. We also present approximation algorithms for generalizations and variants including the problems in which edges have demands and capacities or we seek an edge-dominating set that is connected or a closed walk.; Our approximation algorithms are simply stated; however, our analysis relies intimately on a polyhedral understanding of related problems from matching theory. In an attempt to expand this frontier, we explore several polyhedra corresponding to variants of the Edge Cover Problem, a matching problem in disguise, and present a ½-integral relaxation for the General Factor Problem, one of the most general matching problems whose optimization complexity is unresolved. |
