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 11 of 11 for “"degree bounded"”.
-
Survivable network design problems with element and vertex connectivity requirements
In this thesis, we consider degree-bounded element-connectivity Survivable Network Design Problem (Elem-SNDP) and degree-bounded Rooted k-outconnectivity Problem. We suggest bicriteria approximation algorithms that are motivated by Ene and Vakilian's work in [1] and Lau and Zhou's work in [2]. The …
-
Primal-Dual Techniques for Online Algorithms and Mechanisms
… constraints. We initiate the study of degree-bounded graph optimization problems in the online setting by designing an online algorithm with a tight competitive ratio for the degree-bounded Steiner forest problem. We hope these techniques establishes a starting point for the analysis of …
-
Iterative Rounding Approximation Algorithms in Network Design
… can construct a (2,2B + 3)-approximation for the degree bounded ELC problem, and this thesis provides the proof. We provide some structural results for basic feasible solutions of the Prize-Collecting Steiner Tree problem, and introduce a new problem that arises, which we call the Prize-Collecting …
-
Algebraic degrees of stretch factors in mapping class groups
… a stretch factor is an algebraic integer with degree bounded above by 6g-6. However, little is known about which degrees occur. Using train tracks on surfaces, we explicitly construct pseudo-Anosov maps on Sg with orientable foliations whose stretch factor \lambda has algebraic degree 2g. …
-
New Algorithmic Solutions for Some Clustering and Network Design Problems
… location problem. The second part is devoted to degree-bounded network design problems. The degree constraints require the degree of each node being bounded by certain quantity, which often makes a network design problem much harder. We aim to design algorithms for several fundamental network …
-
Parameterized algorithms and computational lower bounds: a structural approach
… search space. For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an âÂÂalmost-globalâ analysis of the search tree. We also show that an important structural property of the underlying graphs â the …
-
Critical Exponents and Stabilizers of Infinite Words
… exponents of such words are algebraic, of a degree bounded by the alphabet size. Under certain conditions, our proof implies an algorithm for computing the critical exponent. We demonstrate our method by computing the critical exponent of some families of infinite words. In particular, in …
-
An information theoretic approach to structured high-dimensional problems
… discrete and Gaussian Markov networks based on degree-bounded graphs. The problem of accurately learning the structure of discrete Markov networks, based on power-law graphs generated from the con figuration model, is also studied. The eff ect of power-law exponent value on the hardness of the …
-
On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems
… of Vertex Cover (resp. Independent Set) in degree bounded graphs.
-
Routing, Scheduling, and Sorting in Consolidated Networks
… departure times at the majority of the high-degree nodes in the network, an aspect characteristic of region-based networks. A second challenge is handling static storage constraints without leading to a weak relaxation in each iteration. To mitigate these limitations, an arc-based DDD …