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 20 of 192 for “"integrality"”.
-
Integrality theorems for symmetric instantons
… particular allows for a number of '(algebraic) integrality' results for solutions to the symmetric instanton equations. Using the equivariant index theorem the 'SU(2) restriction' ansatz used in previous work is proved to give the only non-trivial class of solutions to the symmetric instanton …
-
Integrality in max-linear systems
This thesis deals with the existence and description of integer solutions to max-linear systems. It begins with the one-sided systems and the subeigenproblem. The description of all integer solutions to each of these systems can be achieved in strongly polynomial time. The main max-linear systems …
-
On the Integrality Gap of Directed Steiner Tree Problem
… for any constant ε > 0. Furthermore, the integrality gap of a natural LP relaxation can be as bad as Ω(√|X|).  We demonstrate that l rounds of the Sherali-Adams hierarchy suffice to reduce the integrality gap of a natural LP relaxation for Directed Steiner Tree in l-layered graphs from Ω( …
-
The integrality gap of the asymmetric travelling salesman problem
… costs are metric. In this thesis we study the integrality gap for the ATSP, i.e. the worst-case ratio between the ATSP and its linear programming relaxation ATSPLP. The ATSPLP provides a lower bound for the ATSP, which is useful for branch and bound solution techniques as well as for providing …
-
Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations
… related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build …
-
An Algorithm for Stable Matching with Approximation up to the Integrality Gap
… Our result matches the known lower bound on the integrality gap for the associated LP formulation.
-
Line bundles and integrality conditions in quantum mechanics and quantum field theory
… sufficient condition for the existence of the integrality condition is obtained. The role of torsion parts in the first homology group of the configuration space is clarified. A possible extension to the higher dimensional vector bundle and its physical meanings are considered, too. Finally …
-
Discovering Discrete Structures using SDP Relaxation: Hidden Integrality, Statistical Optimality and Semirandom Robustness
Understanding discrete structures of data has been an important and ongoing effort in the communities of machine learning, optimization and statistics. We will introduce the problem under a wide range of generative models, including the well-known Stochastic Block Model and Gaussian Mixture Model. …
-
The Processing of Stimulus Attributes: Evidence for Dual-Task Integrality (Erp, P300, Time Sharing)
… three factors likely to influence the integrality between tasks: inter-task redundancy, the physical proximity of tasks and the task relevant objects. The resource structure associated with these integrated dual-task pairs is inferred from changes in the amplitude of the P300 component …
-
Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem
… and certain subclasses thereof. We analyze the integrality gap of the natural LP relaxation within the framework of small-diameter decompositions. By introducing novel tools, we improve the best known lower bound on this integrality gap from $2$ to $\tfrac{20}{9}$ for the family of cactus …
-
On the Integrality Gap of the Subtour Relaxation of the Traveling Salesman Problem for Certain Fractional 2-matching Costs
This thesis provides new bounds on the strength of the subtour relaxation of the Traveling Salesman Problem (TSP) for fractional 2-matching cost instances whose support graphs have no fractional cycles larger than five vertices. This work provides insight for improving approximation heuristics for …
-
Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps
… analysis of this linear program's \emph{integrality gap} (which dictates its use in proving approximation guarantees) has not been improved in nearly 40 years of active research. This thesis contributes to two main avenues of TSP research towards breaking these bottlenecks, both of which …
-
On Complete Integral Closure of Integral Domains
… polynomial with coefficients in D. The notion of integrality has roots in Dedekind's work with algebraic integers, and was later developed more rigorously by Emmy Noether. Different variations or generalizations of integrality have since been studied, including almost integrality and …
-
The Limit of the Small I-function for Calabi-Yau GIT Targets and an Application to the Integrality of the Mirror Map
… As a corollary, we obtain an application to the integrality of the mirror map for a family of Calabi-Yau GIT targets.
-
On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems
… There, the measure of efficiency is the integrality gap which sets the approximation limitation of the algorithms based on these relaxations. In this work we study the integrality gap of families of strong LP and SDP relaxations for a number of combinatorial optimization problems. The …
Page 1 of 10