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 20 for “"strongly polynomial"”.

  1. On Vegh's Strongly Polynomial Algorithm for Generalized Flows

    This thesis contains an exposition of the new strongly polynomial algorithm for the generalized flow problem by Laszlo Vegh (2013). It has been a long-standing open question whether such an algorithm exists, until it was resolved by Vegh in 2013. Generalized flows have many applications in economic …

    waterloo Repository record for On Vegh's Strongly Polynomial Algorithm for Generalized Flows (opens in a new tab)

  2. Integrality in max-linear systems

    … to each of these systems can be achieved in strongly polynomial time. The main max-linear systems that we consider include the eigenproblem, and the problem of determining whether a matrix has an integer vector in its column space. Also the two-sided systems, as well as max-linear programming …

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

  3. Matchings with a size constraint

    … and (g, f)-factors. This thesis aims at polynomial algorithms which in addition have other properties. In particular, we develop a polynomial algorithm which can find optimal solutions of each possible size for weighted matching problem, and a strongly polynomial algorithm which can find …

    ubc Repository record for Matchings with a size constraint (opens in a new tab) Download PDF for Matchings with a size constraint (opens in a new tab)

  4. Linear Sum Assignment Algorithms for Distributed Multi-robot Systems

    … new features. For the former, we first propose a strongly polynomial assignment sensitivity analysis algorithm as well as a means to measure the assignment uncertainties; after that we propose a novel method to address problems of multi-robot routing and formation morphing, the trajectories of …

    tamu Repository record for Linear Sum Assignment Algorithms for Distributed Multi-robot Systems (opens in a new tab)

  5. Polyhedral Diameters and Applications to Optimization

    … pivot rule that makes the Simplex method run in polynomial time. Circuit-augmentation algorithms are generalizations of the Simplex method, where in each step one is allowed to move along a fixed set of directions, called the circuits, that is a superset of the edges of a polytope. The number of …

    waterloo Repository record for Polyhedral Diameters and Applications to Optimization (opens in a new tab)

  6. Algorithms for weighted multidimensional search and perfect phylogeny

    … bad constraints, the problems can be solved in strongly polynomial time by combinatorial algorithms. Second, the number of bad constraints is fixed. As part of our solution to these problems, we extend Cole's circuit simulation approach and develop a weighted version of Megiddo's …

    iastate Repository record for Algorithms for weighted multidimensional search and perfect phylogeny (opens in a new tab)

  7. Special and structured matrices in max-plus algebra

    The aim of this thesis is to present efficient (strongly polynomial) methods and algorithms for problems in max­algebra when certain matrices have special entries or are structured. First, we describe all solutions to a one-sided parametrised system. Next, we consider special cases of two-sided …

    birmingham Download PDF for Special and structured matrices in max-plus algebra (opens in a new tab)

  8. Fast and Reliable Optimization for Dynamic Decision-making Under Uncertainty

    … that policy gradient methods can solve MDPs in strongly-polynomial time. This result shows popular gradient-based approaches can efficiently find exact solutions when the model is known, and it matches the strongly-polynomial runtime of simplex and Howard’s policy iteration proven by Ye. In …

    gatech Repository record for Fast and Reliable Optimization for Dynamic Decision-making Under Uncertainty (opens in a new tab)

  9. Algorithms for fair division through competitive equilibrium

    … then the number of pivots in the algorithm is strongly polynomial when the mixed manna contains only bads, providing additional evidence to the practicality of my approach. Second, I focus on the case of indivisible goods. Various fairness notions have been proposed with the rapidly growing …

    uiuc Repository record for Algorithms for fair division through competitive equilibrium (opens in a new tab)

  10. The Polyhedral Geometry of Graphical Designs

    … of a positively weighted graph, and we provide a strongly polynomial time algorithm for this construction. As a stepping stone, we show that given an appropriate orthogonal basis of $\mathbb{R}^n$ and a partition of these basis vectors, there is a positively weighted graph which has Laplacian …

    washington Repository record for The Polyhedral Geometry of Graphical Designs (opens in a new tab)

  11. Matching theory: subgraphs with degree constraints and other properties

    … number of inequalities can be reduced to a polynomial number of inequalities. The second problem is the general factor problem. Let G = (V, E) be a multigraph. An arbitrary subset BL, of {O, 1,2,. . . , deg(v)} is assigned to each vertex ʋ E Ʋ. We call a B-factor a spanning subgraph F of G …

    ubc Repository record for Matching theory: subgraphs with degree constraints and other properties (opens in a new tab) Download PDF for Matching theory: subgraphs with degree constraints and other properties (opens in a new tab)

  12. Cost/revenue allocation on networks

    … problems considered in my thesis. Efficient, strongly polynomial algorithms are then developed for calculating the nucleolus of these games. Although the general approach in Chapters 2 and 3 is similar, the techniques used in each chapter for developing the computational algorithms are …

    ubc Repository record for Cost/revenue allocation on networks (opens in a new tab) Download PDF for Cost/revenue allocation on networks (opens in a new tab)

  13. Multi-stage Stochastic Programming Models in Production Planning

    … the problem structure. Both algorithms are strongly polynomial, and therefore much more efficient than the Simplex method. Next, motivated by applications in semiconductor tool planning, we develop a general capacity planning problem under uncertainty. Using a scenario tree to model the …

    gatech Repository record for Multi-stage Stochastic Programming Models in Production Planning (opens in a new tab)

  14. Efficient Algorithms for Market Equilibria

    … desirable. The goal of this thesis is to provide polynomial time algorithms for various market models. Two basic market models are the Fisher model: one in which there is a demarcation between buyers and sellers, buyers are interested in the goods that the sellers possess, and sellers are only …

    gatech Repository record for Efficient Algorithms for Market Equilibria (opens in a new tab)

  15. On the Design, Analysis, and Implementation of Algorithms for Selected Problems in Graphs and Networks

    … G contain a negative cost cycle? We discuss two polynomial time algorithms for solving the UNCCD problem: the b-matching approach and the T-join approach. We obtain new results for the case where the edge costs are integers in the range {lcub}--K ·· K{rcub}, where K is a positive constant. We …

    wvu Repository record for On the Design, Analysis, and Implementation of Algorithms for Selected Problems in Graphs and Networks (opens in a new tab)

  16. Natural and efficient dynamics through convex optimization

    … stable point with high probability.We present a polynomial time algorithm for the k-facility reallocation problem. This problem was proposed as a generalization of the classical k-median optimization problem, where the positions of the requests lie on the real line but may change over time. Our …

    greece Repository record for Natural and efficient dynamics through convex optimization (opens in a new tab)

  17. Convex Optimization Over Integer Points

    … using the ellipsoid method to establish the polynomial solvability of a broad range of combinatorial optimization problems. When the integer minimizer condition fails, the problem typically becomes computationally intractable, as witnessed by the NP-Hardness of the Integer Linear Programming …

    washington Repository record for Convex Optimization Over Integer Points (opens in a new tab)

  18. Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs

    … game families can be solved in deterministic polynomial time. Policy iteration is one of the most important algorithmic schemes for solving infinitary payoff games. It is parameterized by an improvement rule that determines how to proceed in the iteration from one policy to the next. It is a …

    lmu-germany Repository record for Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs (opens in a new tab)

  19. Probabilistic bicriteria models : sampling methodologies and solution strategies

    … approximation: (i) can be computed in strongly polynomial time by relying on a reformulation as a max-flow problem via the well-studied selection problem; and, (ii) converges uniformly to the true efficient frontier, when the latter is convex. We conclude with numerical studies that …

    texas Repository record for Probabilistic bicriteria models : sampling methodologies and solution strategies (opens in a new tab)