Title: Polyhedral techniques for graphic covering problems
Abstract: 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.
Publication Year: 2002
Publication Date: 2002-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 11
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot