New approaches to integer programming

Show simple item record Chandrasekaran, Karthekeyan en_US 2012-09-20T18:20:30Z 2012-09-20T18:20:30Z 2012-06-28 en_US
dc.description.abstract Integer Programming (IP) is a powerful and widely-used formulation for combinatorial problems. The study of IP over the past several decades has led to fascinating theoretical developments, and has improved our ability to solve discrete optimization problems arising in practice. This thesis makes progress on algorithmic solutions for IP by building on combinatorial, geometric and Linear Programming (LP) approaches. We use a combinatorial approach to give an approximation algorithm for the feedback vertex set problem (FVS) in a recently developed Implicit Hitting Set framework. Our algorithm is a simple online algorithm which finds a nearly optimal FVS in random graphs. We also propose a planted model for FVS and show that an optimal hitting set for a polynomial number of subsets is sufficient to recover the planted subset. Next, we present an unexplored geometric connection between integer feasibility and the classical notion of discrepancy of matrices. We exploit this connection to show a phase transition from infeasibility to feasibility in random IP instances. A recent algorithm for small discrepancy solutions leads to an efficient algorithm to find an integer point for random IP instances that are feasible with high probability. Finally, we give a provably efficient implementation of a cutting-plane algorithm for perfect matchings. In our algorithm, cuts separating the current optimum are easy to derive while a small LP is solved to identify the cuts that are to be retained for later iterations. Our result gives a rigorous theoretical explanation for the practical efficiency of the cutting plane approach for perfect matching evident from implementations. In summary, this thesis contributes to new models and connections, new algorithms and rigorous analysis of well-known approaches for IP. en_US
dc.publisher Georgia Institute of Technology en_US
dc.subject Random graphs en_US
dc.subject Feedback vertex set en_US
dc.subject Cutting plane method en_US
dc.subject Integer program en_US
dc.subject Discrepancy en_US
dc.subject Random en_US
dc.subject Matching en_US
dc.subject.lcsh Integer programming
dc.subject.lcsh Programming (Mathematics)
dc.subject.lcsh Algorithms
dc.title New approaches to integer programming en_US
dc.type Dissertation en_US PhD en_US
dc.contributor.department Algorithms, Combinatorics, and Optimization en_US
dc.description.advisor Committee Chair: Vempala, Santosh; Committee Member: Ahmed, Shabbir; Committee Member: Cook, William; Committee Member: Dey, Santanu; Committee Member: Karp, Richard; Committee Member: Nemhauser, George en_US

Files in this item

Files Size Format View
chandrasekaran_karthekeyan_201208_phd.pdf 963.6Kb PDF View/ Open

This item appears in the following Collection(s)

Show simple item record