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 11 of 11 for “"Lift-and-project"”.
-
A Comprehensive Analysis of Lift-and-Project Methods for Combinatorial Optimization
In both mathematical research and real-life, we often encounter problems that can be framed as finding the best solution among a collection of discrete choices. Many of these problems, on which an exhaustive search in the solution space is impractical or even infeasible, belong to the area of …
-
On the Polyhedral Lift-and-Project Rank Conjecture for the Fractional Stable Set Polytope
In this thesis, we study the behaviour of Lovasz and Schrijver's lift-and-project operators N and N_0 while being applied recursively to the fractional stable set polytope of a graph. We focus on two related conjectures proposed by Liptak and Tuncel: the N-N_0 Conjecture and Rank Conjecture. First, …
-
Point cover problem in 3D
… the point cover problem. We study the Lift-and-Project relaxation of the standard IP to obtain lower bounds. This method is used to strengthen the integrality gap of a problem. Our experimental results show that the Lagrangian relaxation method gives very good lower bounds at reasonable …
-
Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations
… Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of …
-
Semidefinite Cuts and Partial Convexification Techniques with Applications to Continuous Nonconvex Optimization, Stochastic Integer Programming, and Facility Layout Problems
… efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use …
-
Limitations of linear programming as a model of approximate computation
… has proved to be one of the most powerful and widely used tools inalgorithm design and especially in the design of approximation algorithms. It has provedits expressive power by modeling diverse types of problems in planning, routing, scheduling,assignment, and design. The popularity of …
-
A branch, price, and cut approach to solving the maximum weighted independent set problem
… problem (MWISP) is one of the most well-known and well-studied NP-hard problems in the field of combinatorial optimization. In the first part of the dissertation, I explore efficient branch-and-price (B&P) approaches to solve MWISP exactly. B&P is a useful integer-programming tool for solving …
-
On the Integrality Gap of Directed Steiner Tree Problem
… G = (V,E) with edge costs, a root vertex r ∈ V, and a terminal set X ⊆ V . The goal is to find the cheapest subset of edges that contains an r-t path for every terminal t ∈ X. The only known polylogarithmic approximations for Directed Steiner Tree run in quasi-polynomial time and the best …
-
On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems
… e.g. through the use of semidefinite programming and hardness of approximation, e.g. the development of Probabilistically Checkable Proofs and Unique Games Conjecture. Trying to prove lower bounds for the approximation threshold of an optimization problem, one could take one of two approaches. In …
-
Approximation Algorithms for Path TSP, ATSP, and TAP via Relaxations
… the general metric s-t path TSP. [An, Kleinberg, and Shmoys, STOC 2012] improved on the long standing 5/3-approximation factor and presented an algorithm that achieves an approximation factor of (1+\sqrt{5})/2 \approx 1.61803. Later, [Sebo, IPCO 2013] further improved the approximation factor to …
-
Decomposition Methods in Column Generation and Data-Driven Stochastic Optimization
… arising in two-stage stochastic optimization and the related Dantzig-Wolfe decomposition. We start with a deterministic setting, where we consider linear programs with a block-structure, but data cannot be stored centrally due to privacy concerns or decentralized storage of large datasets. The …