Show simple item record

dc.contributor.authorChandrasekaran, Karthekeyanen_US
dc.date.accessioned2012-09-20T18:20:30Z
dc.date.available2012-09-20T18:20:30Z
dc.date.issued2012-06-28en_US
dc.identifier.urihttp://hdl.handle.net/1853/44814
dc.description.abstractInteger 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.publisherGeorgia Institute of Technologyen_US
dc.subjectRandom graphsen_US
dc.subjectFeedback vertex seten_US
dc.subjectCutting plane methoden_US
dc.subjectInteger programen_US
dc.subjectDiscrepancyen_US
dc.subjectRandomen_US
dc.subjectMatchingen_US
dc.subject.lcshInteger programming
dc.subject.lcshProgramming (Mathematics)
dc.subject.lcshAlgorithms
dc.titleNew approaches to integer programmingen_US
dc.typeDissertationen_US
dc.description.degreePhDen_US
dc.contributor.departmentAlgorithms, Combinatorics, and Optimizationen_US
dc.description.advisorCommittee Chair: Vempala, Santosh; Committee Member: Ahmed, Shabbir; Committee Member: Cook, William; Committee Member: Dey, Santanu; Committee Member: Karp, Richard; Committee Member: Nemhauser, Georgeen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record