Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 3 of 3 for “"Integrality ratio"”.

  1. Approximation Algorithms for Path TSP, ATSP, and TAP via Relaxations

    … small \epsilon, 0<\epsilon<<1, we prove that the integrality ratio for level t of the SA system starting with the standard LP relaxation of ATSP is at least 1+(1-\epsilon)/(2t+3). For a further relaxation of ATSP called the balanced LP relaxation, we obtain an integrality ratio lower bound of …

    waterloo Repository record for Approximation Algorithms for Path TSP, ATSP, and TAP via Relaxations (opens in a new tab)

  2. Decomposition-based methods for Connectivity Augmentation Problems

    … to attain a significantly better approximation ratio. Next, we look at the special case when k=2. This case is equivalent to what is known as the Cactus Augmentation problem. A recent result by Cecchetto, Traub and Zenklusen give a 1.393-approximation algorithm for this problem using the same …

    waterloo Repository record for Decomposition-based methods for Connectivity Augmentation Problems (opens in a new tab)

  3. Hardness results and approximation algorithms for some problems on graphs

    … Steiner Tree Packing problem has an integrality ratio of $2-\epsilon$ in planar graphs.

    waterloo Repository record for Hardness results and approximation algorithms for some problems on graphs (opens in a new tab)