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 22 for “"Linear programming relaxations"”.

  1. Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations

    … has been studied in numerous variants, and linear programming has played an important role in the design of approximation algorithms for these problems. In this thesis, we study two versions of the traveling salesman problem and present approximation algorithms for them based on the …

    cornell Repository record for Approximation Algorithms For Traveling Salesman Problems Based On Linear Programming Relaxations (opens in a new tab)

  2. Marginal Productivity Indices and Linear Programming Relaxations for Dynamic Resource Allocation in Queueing Systems

    … as the resource; we construct hierarchical Linear Programming (LP) relaxations for the buffer sharing problem and propose an MPI based heuristic with its performance evaluated by discrete event simulation. In our study, the admission control model is used as the building block for the MPI …

    lund Repository record for Marginal Productivity Indices and Linear Programming Relaxations for Dynamic Resource Allocation in Queueing Systems (opens in a new tab) Download PDF for Marginal Productivity Indices and Linear Programming Relaxations for Dynamic Resource Allocation in Queueing Systems (opens in a new tab)

  3. A novel weighted rank aggregation algorithm with applications in gene prioritization

    … Kendall distances. The algorithms represent linear programming relaxations of integer programs that involve variables reflecting partial orders of three or more candidates. Our simulation results indicate that the linear programs give near-optimal performance for a number of important voting …

    uiuc Repository record for A novel weighted rank aggregation algorithm with applications in gene prioritization (opens in a new tab)

  4. A reformulation-linearization based implicit enumeration algorithm for the rectilinear distance location-allocation problem

    … thesis is concerned with the analysis of a Rectilinear Distance Location Allocation Problem, where the costs are directly proportional to rectilinear distances and the amount shipped. The problem is formulated as a Mixed Integer Bilinear Programming Problem and as a Discrete Location Allocation …

    vt Repository record for A reformulation-linearization based implicit enumeration algorithm for the rectilinear distance location-allocation problem (opens in a new tab)

  5. GRAPH CUTS, SUM-OF-SUBMODULAR FLOW, AND LINEAR PROGRAMMING: EFFECTIVE INFERENCE IN HIGHER-ORDER MARKOV RANDOM FIELDS

    … Sum-of-Submodular optimization. And finally linear programming relaxations based on the Local Marginal Polytope, which together with Sum-of-Submodular flow results in the highly effective primal-dual algorithm SoSPD. This thesis presents all mathematical background for these algorithms, as …

    cornell Repository record for GRAPH CUTS, SUM-OF-SUBMODULAR FLOW, AND LINEAR PROGRAMMING: EFFECTIVE INFERENCE IN HIGHER-ORDER MARKOV RANDOM FIELDS (opens in a new tab)

  6. The polyhedral structure of certain combinatorial optimization problems with application to a naval defense problem

    … partitioning problem, and the quadratic zero-one programming problem, and applies related techniques to solve a practical combinatorial naval defense problem. In Part I of this research effort, we present new results on the polyhedral structure of the foregoing combinatorial optimization problems. …

    vt Repository record for The polyhedral structure of certain combinatorial optimization problems with application to a naval defense problem (opens in a new tab)

  7. Characterizing Structurally Cohesive Clusters in Networks: Theory and Algorithms

    … More specifically, we consider graph theoretic relaxations of clique as models for characterizing structurally cohesive and robust subgroups, developing strong upper bounds for the maximum clique problem, and present a new relaxation that is useful in clustering applications. We consider the …

    tamu Repository record for Characterizing Structurally Cohesive Clusters in Networks: Theory and Algorithms (opens in a new tab)

  8. Optimal Graph Coverings with Connected Subgraphs

    … heuristic or approximation algorithms, integer programming formulations, or polyhedral studies to strengthen the respective linear programming relaxations. The thesis reviews both fields and gives a categorization and overview of the problems, approaches, and results. An important subproblem is …

    fu-berlin Repository record for Optimal Graph Coverings with Connected Subgraphs (opens in a new tab)

  9. Resource constrained shortest paths and extensions

    In this thesis, we use integer programming techniques to solve the resource constrained shortest path problem (RCSPP) which seeks a minimum cost path between two nodes in a directed graph subject to a finite set of resource constraints. Although NP-hard, the RCSPP is extremely useful in practice …

    gatech Repository record for Resource constrained shortest paths and extensions (opens in a new tab)

  10. On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs

    … has been substantial work on obtaining tight linear-programming relaxations for the Steiner tree problem. Many undirected and directed formulations have been proposed in the course of the last 25 years; their use, however, is to this point mostly restricted to the field of exact optimization. …

    waterloo Repository record for On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs (opens in a new tab)

  11. Nondifferentiable optimization algorithms with application to solving Lagrangian dual problems

    … as well as in the context of other mathematical programming approaches such as Dantzig-Wolfe decomposition, Benders decomposition, Lagrangian duality, penalty function methods, and minimax problems. The importance and necessity of having effective solution methods for NDO problems has long been …

    vt Repository record for Nondifferentiable optimization algorithms with application to solving Lagrangian dual problems (opens in a new tab)

  12. A Discrete Optimization Approach to Solve a Reader Location Problem for Estimating Travel Times

    … optimization approach based on the Reformulation-Linearization Technique coupled with Semidefinite Programming concepts is designed to solve the formulated reader location problem. This approach can be used to derive alternative equivalent formulations of the problem that vary in the degree of …

    vt Repository record for A Discrete Optimization Approach to Solve a Reader Location Problem for Estimating Travel Times (opens in a new tab)

  13. Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization

    … and lower bounds related to applications of linear programs in combinatorial optimization. The following "Steiner tree problem" is central: given a graph with a distinguished subset of required vertices, and costs for each edge, find a minimum-cost subgraph that connects the required …

    waterloo Repository record for Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization (opens in a new tab)

  14. Postman Problems on Mixed Graphs

    … arcs at least once. We prove that two well-known linear programming relaxations of this problem are equivalent. The <i>extra cost</i> of a mixed postman tour <i>T</i> is the cost of <i>T</i> minus the cost of the edges and arcs of <i>M</i>. We prove that it is <i>NP</i>-hard to approximate the …

    waterloo Repository record for Postman Problems on Mixed Graphs (opens in a new tab)

  15. Randomized Kernel Rounding for Routing, Scheduling, and Machine Learning

    … intermediate solutions due to convex/linear relaxations of the problems, using kernels that can be adapted for best performance, can significantly improve approximation guarantees for multiple such problems. The first set of problems that we study, in Chapter 2, are routing problems …

    gatech Repository record for Randomized Kernel Rounding for Routing, Scheduling, and Machine Learning (opens in a new tab)

  16. Algorithmic aspects of connectivity, allocation and design problems

    … and then using its polynomial time solvable linear programming relaxation for the design and analysis of such algorithms. Such a technique is called the LP-based technique. In this thesis, we study the algorithmic aspects of three classes of combinatorial optimization problems using LP-based …

    gatech Repository record for Algorithmic aspects of connectivity, allocation and design problems (opens in a new tab)

  17. Polynomial and indefinite quadratic programming problems: algorithms and applications

    … with the global optimization of polynomial programming problems, and a detailed treatment of its particular special case, the indefinite quadratic programming problem. Polynomial programming problems are generally nonconvex, involving the optimization of a polynomial objective function over …

    vt Repository record for Polynomial and indefinite quadratic programming problems: algorithms and applications (opens in a new tab)

  18. An optimal replacement-design model for a reliable water distribution network system

    … and an easy-to-solve convex cost network flow programming subproblem. The master program operates in the space of the structural design variables, while the subproblem determines flows as well as heads via its primal and dual optimal solutions. The coordination between the master program and …

    vt Repository record for An optimal replacement-design model for a reliable water distribution network system (opens in a new tab)

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

    Linear programming (LP) relaxations provide a powerful technique to design approximation algorithms for combinatorial optimization problems. In the first part of the thesis, we study the metric s-t path Traveling Salesman Problem (TSP) via LP relaxations. We first consider the s-t path graph-TSP, a …

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

Page 1 of 2