New Bounds on Integrality Gaps by Constructing Convex Combinations

This dissertation studies the integrality gap of linear programming relaxations of integer programs. The integrality gap of a continuous relaxation of the sets of lattice

points corresponding to integer feasible solutions is the worst case ratio between the cost of an integer feasible solution and the optimal value of the continuous relaxation.

The main focus in the ?first part of the thesis is on the Traveling Salesperson Problem (TSP) and the 2-edge-connected multigraph problem (2ECM). In TSP and 2ECM we are given n vertices with costs on pairs of vertices. We consider cost functions obeying triangle inequality. In TSP the goal is to fi?nd the minimum cost Hamiltonian cycle and

in the 2ECM the goal is to ?find the minimum cost 2-edge-connected subgraph. Both problems can be formulated via a linear programming relaxation known as the subtour elimination relaxation. The most general case for TSP and 2ECM has resisted approximation algorithms (and upper bounds on the integrality gap with the subtour

elimination relaxation) better than 3/2 for decades.

In Chapter 3 we consider TSP and 2ECM on node-weighted graphs. These are instances where the cost on the pairs of vertices arise from a shortest path between the pair in a node-weighted graph, a graph with edge weights arising from adding the costs of its endpoints. First we show that for 3-edge-connected cubic graphs, there is a 7/5 approximation algorithm for the node-weighted TSP and a 13/10-approximation for the node-weighted 2ECM. The main tool for both algorithms is the fact that 3-edgeconnected

cubic graphs contain 2-factors covering all their small edge cuts. We extend this result to subcubic graphs by providing a decomposition of a point of the subtour elimination relaxation into a convex combination of connected multigraphs, each covering 2-edge cuts an even number of times. An application of this decomposition leads to a

17/12 -approximation algorithm for node-weighted 2ECM on subcubic graphs. Chapter 4 focuses on the Uniform Cover Problem for TSP and 2ECM. We establish this framework as a way to approach the most general case of TSP and 2ECM. As a ?first result, we give the ?first positive answer to Seb}o et al. [SBS14] regarding the uniform cover problem for TSP by showing that for a 3-edge-connected cubic graph, the incidence vector of G multiplied by 18=19 can be decomposed into a convex combination of solutions for the TSP: this is equivalent to a 27/19-approximation for TSP on such instances. We also provide a 45/34 -approximation for 2ECM on such instances. This is the first bound below 4

3 that can be proved via an efficient rounding algorithm. Improving this factor further requires a technique commonly known as \gluing". We show how gluing on 3-edge cuts reduces our problems to more structured instances. For such structured instances we use a novel application of a rainbow 1-tree decomposition that serves a top-down coloring algorithm in order to improve the factor of 45/34 ≈ 1:323 to 123/94 ≈ 1:308. In Chapter 5 our focus is on half-integer points of the subtour elimination relaxation

motivated by the conjecture of Schalekamp, Williamson, van Zuylen [SWvZ13] that the largest integrality gap is achieved for instances where the optimal solution of the subtour

elimination relaxation is half-integer. Our focus is on fundamental classes that are a class of interesting yet highly structured points in the subtour elimination relaxation.

In particular, we study half-square points and half-triangle points. For half-squarepoints we provide a 9/7 -approximation for 2ECM and for half-triangle points we show a ( 6/5 + 1/120 )-approximation for 2ECM. In Chapter 6 we investigate the possibility of gluing the solutions for T SP over 3-edge cuts. Gluing over 3-edge cuts has proven to be successful for 2-edge-connected subgraphs but there is not much known in this direction for gluing connected multigraphs. We introduce a novel approach of gluing solutions to the TSP based on different parts of

a tour: (i) the connected skeleton of a solution which is a connected subgraph and (ii) the parity correction part of the solution that augments the connected skeleton into an

Eulerian connected multigraph. Using this approach we show that for a half-integer point x of the subtour elimination relaxation, we can reduce the usage of edges with x-value 1 from the 3/2 of Christo?des' algorithm to 3/2 - 1/20 while keeping the usage of edges with x-value of 1 2 the same as Christo?des' algorithm. A direct consequence of this result is for the Uniform Cover Problem for TSP, where we show that for a 3-edge-connected cubic graph, the incidence vector of G multiplied by 17/18 can be decomposed into a convex combination of solutions for the TSP: In this way we improve

the 27/19 -approximation algorithm in Chapter 4 to a 17/12 -approximation algorithm for TSP on these instances.

In the fi?nal chapter of this thesis, we focus on general binary integer programs (binary IPs) and show an efficient algorithm, called the Fractional Decomposition Tree Algorithm (FDT), that provides an upper bound on the integrality gap of an instance of a binary IP with its linear programming relaxation. As a stepping stone, we design an efficient algorithm for ?finding a feasible integer solution to binary IPs with bounded integrality gap which may be of independent interest. We extend FDT to ?find convex combinations of 2-edge-connected multigraphs which is a non-binary problem. We run experiments and compare upper bounds provided by FDT with that of polyhedral version of Christo?des' algorithm.