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"”.

  1. 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 …

    waterloo Repository record for Integrality theorems for symmetric instantons (opens in a new tab)

  2. 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 …

    birmingham Download PDF for Integrality in max-linear systems (opens in a new tab)

  3. 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 Ω( …

    waterloo Repository record for On the Integrality Gap of Directed Steiner Tree Problem (opens in a new tab)

  4. 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 …

    ottawa-retro Repository record for The integrality gap of the asymmetric travelling salesman problem (opens in a new tab)

  5. 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 …

    toronto-retro Repository record for Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations (opens in a new tab)

  6. 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.

    waterloo Repository record for An Algorithm for Stable Matching with Approximation up to the Integrality Gap (opens in a new tab)

  7. 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 …

    uiuc Repository record for Line bundles and integrality conditions in quantum mechanics and quantum field theory (opens in a new tab)

  8. 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. …

    cornell Repository record for Discovering Discrete Structures using SDP Relaxation: Hidden Integrality, Statistical Optimality and Semirandom Robustness (opens in a new tab)

  9. 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 …

    uiuc Repository record for The Processing of Stimulus Attributes: Evidence for Dual-Task Integrality (Erp, P300, Time Sharing) (opens in a new tab)

  10. 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 …

    waterloo Repository record for Cuts in Optimization and Approximation: Generalized MIR Cutting Plane and Integrality Gap Bounds for the Planar Multicut Problem (opens in a new tab)

  11. 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 …

    rice Repository record for On the Integrality Gap of the Subtour Relaxation of the Traveling Salesman Problem for Certain Fractional 2-matching Costs (opens in a new tab)

  12. 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 …

    cornell Repository record for Fantastic Relaxations of the TSP and How to Bound them: Relaxations of the Traveling Salesman Problem and their Integrality Gaps (opens in a new tab)

  13. 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 …

    clemson Repository record for On Complete Integral Closure of Integral Domains (opens in a new tab)

  14. 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 …

    toronto-retro Repository record for On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems (opens in a new tab)

Page 1 of 10