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 7 of 7 for “"stable set polytope"”.
-
On the Polyhedral Lift-and-Project Rank Conjecture for the Fractional Stable Set Polytope
… 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, we look at the algebraic derivation of new valid inequalities by the operators N and N_0. We then …
-
On The Circuit Diameters of Some Combinatorial Polytopes
The combinatorial diameter of a polytope P is the maximum value of a shortest path between two vertices of P, where the path uses the edges of P only. In contrast to the combinatorial diameter, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, …
-
Independence systems and stable set relaxations
… optimization problems involve the search for subsets of graph elements which satisfy some notion of independence. This thesis develops techniques for optimizing over a class of independence systems and focuses on systems having the vertex set of a finite graph as a ground set. The search for …
-
Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems
… a large and possibly high-dimensional finite set. It is often the case that the set is so large that solving the problem by inspecting all the elements is intractable. One approach to circumvent this issue is by exploiting the combinatorial structure of the set (and possibly the function) and …
-
A Comprehensive Analysis of Lift-and-Project Methods for Combinatorial Optimization
… then approximate their feasible regions using sets that are easier to describe and optimize over. Two of the most prominent mathematical models that are used to obtain these approximations are linear programs (LPs) and semidefinite programs (SDPs). The study of these relaxations started to gain …
-
Combinatorial methods in differential algebra
… space of the fat point defined by xm and the stable set polytope of a perfect graph. We prove that the dimension of the coordinate ring of the scheme defined by polynomial arcs of degree less than or equal to n is a polynomial in m of degree n + 1. This is based on Zobnin’s result which states …
-
Geometric Ramifications of the Lovász Theta Function and Their Interplay with Duality
… Lovasz theta function and the associated convex sets known as theta bodies are fundamental objects in combinatorial and semidefinite optimization. They are accompanied by a rich duality theory and deep connections to the geometric concept of orthonormal representations of graphs. In this thesis, …