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 27 for “"Combinatorial Algorithm"”.

  1. Improving the efficiency of dynamic traffic assignment through computational methods based on combinatorial algorithm

    … a suite of computational methods based on the combinatorial approach for dynamic traffic assignment was developed in this dissertation. At first, a new polynomial run time combinatorial algorithm for DTA was developed. The combinatorial DTA (CDTA) model complements and aids simulation-based DTA …

    texas Repository record for Improving the efficiency of dynamic traffic assignment through computational methods based on combinatorial algorithm (opens in a new tab)

  2. Algorithmic and statistical properties of filling elements of a free group, and quantitative residual properties of gamma-limit groups

    … For the free group of rank two, we construct a combinatorial algorithm to determine whether or not a given finitely generated subgroup is filling. In higher ranks, we discuss two types of non-filling subgroups: those contained in loop vertex subgroups and those contained in segment vertex …

    uiuc Repository record for Algorithmic and statistical properties of filling elements of a free group, and quantitative residual properties of gamma-limit groups (opens in a new tab)

  3. A primal-dual algorithm for the maximum charge problem with capacity constraints

    … We use the primal-dual approach. We propose a combinatorial algorithm for solving the dual of the restricted primal and show that the primal-dual algorithm runs in a polynomial time.

    lethbridge Repository record for A primal-dual algorithm for the maximum charge problem with capacity constraints (opens in a new tab)

  4. Covering points with axis parallel lines

    … solution to the problem. We also propose a combinatorial algorithm by using the branch and bound technique which gives an optimal integral solution to the point cover problem. Later we implemented another approximation algorithm based on primal-dual and iterative rounding approaches. Finally …

    lethbridge Repository record for Covering points with axis parallel lines (opens in a new tab)

  5. Computational prioritization of cancer driver genes for precision oncology

    … driver alterations, requiring solutions to novel algorithmic problems. Although, the insight on driver alterations is critical to guide selection of appropriate drug therapies for the patient, no specific tools exist to help clinicians contextualize the enormous genomic information when making …

    ubc Repository record for Computational prioritization of cancer driver genes for precision oncology (opens in a new tab) Download PDF for Computational prioritization of cancer driver genes for precision oncology (opens in a new tab)

  6. Combinatorial Knot Floer Homology

    … to compute. In 2006, in a paper titled "A combinatorial Description of Knot Floer Homology", the authors Ciprian Manolescu, Peter Ozsváth, and Sucharit Sarkar discovered an algorithm for purely combinatorial description of knot Floer homology, making its computation, in principle, fully …

    unr Repository record for Combinatorial Knot Floer Homology (opens in a new tab)

  7. Interference minimization for device-to-device (D2D) communications

    … a target sum rate. We propose a two-phase combinatorial algorithm which computes an allocation subject to the sum rate constraint. For the case when all the interference generated is uniform, the algorithm finds an optimal solution in polynomial time. We also evaluate the algorithm …

    lethbridge Repository record for Interference minimization for device-to-device (D2D) communications (opens in a new tab)

  8. Hyperbolic geometry, regular representations and curves on surfaces

    … have nice symmetry properties. As a result, an algorithm to recover the word of a matrix in terms of the generating elements is given. Also, the general criterion for simplicity previously found is further reduced to a system of diophantine equations. In the appendices, another purely …

    rice Repository record for Hyperbolic geometry, regular representations and curves on surfaces (opens in a new tab)

  9. Clustering, weighted sequences, and shortest paths

    … violated preferences.We design a deterministic combinatorial algorithm with a constant approximation factor. A key ingredient in our approach is a novel nearly-optimal pivoting algorithm for Correlation Clustering. This is a deterministic combinatorial algorithm achieving the best approximation …

    greece Repository record for Clustering, weighted sequences, and shortest paths (opens in a new tab)

  10. Combinatorial Algorithms for the Active Time and Busy Time Problems

    … the busy time problem. First, we give a purely combinatorial algorithm for the active time problem which matches its best known approximation ratio (the existing algorithm is based on a rather involved LP rounding scheme). Second, we describe a local search based heuristic for the problem and …

    maryland Repository record for Combinatorial Algorithms for the Active Time and Busy Time Problems (opens in a new tab)

  11. Finite state properties of bounded parthwidth graphs

    The concepts of the treewidth and pathwidth of combinatorial structures have come to play a central role in a number of important developments in discrete mathematics and combinatorial algorithm design. In particular, they are of fundamental importance to several general algorithm design techniques …

    uvic Repository record for Finite state properties of bounded parthwidth graphs (opens in a new tab)

  12. Distribution Theory of Some Nonparametric Statistics via Finite Markov Chain Imbedding Technique

    … et. al. (1993, 1994) discussed power via combinatorial calculations for the scan statistic against a pulse alternative; however, unless certain proper conditions are given, computational difficulties exist. Our work extends their results and provides an alternative way to obtain the …

    manitoba Repository record for Distribution Theory of Some Nonparametric Statistics via Finite Markov Chain Imbedding Technique (opens in a new tab)

  13. Overcoming Computational Complexity Barriers for Optimal Transport in Discrete and Semi-Discrete Settings

    … present an $varepsilon$-additive approximation algorithm for the semi-discrete OT problem that runs in $n^{O(d)}logfrac{C_{max}}{varepsilon}$ time. Our algorithm works for several ground distances, including the $ell_p$-norm and the squared-Euclidean distance. 2. Combinatorial algorithm for …

    vt Repository record for Overcoming Computational Complexity Barriers for Optimal Transport in Discrete and Semi-Discrete Settings (opens in a new tab)

  14. Annealing and Tempering for Sampling and Counting

    … with only a few notable exceptions, most known algorithms for approximately uniform sampling and approximate counting rely on the MCMC method. This thesis focuses on algorithms that use MCMC combined with an algorithm from optimization called simulated annealing, for sampling and counting …

    gatech Repository record for Annealing and Tempering for Sampling and Counting (opens in a new tab)

  15. Network flow algorithms for wireless networks and design and analysis of rate compatible LDPC codes

    … recently. Motivated by this model, an improved combinatorial algorithm is considered for finding the unicast capacity for wireless information flow on such deterministic networks in the first part of this</p> <p>thesis. Our algorithm fully explores the useful combinatorial features intrinsic in …

    iastate Repository record for Network flow algorithms for wireless networks and design and analysis of rate compatible LDPC codes (opens in a new tab)

  16. Occlusion reasoning for multiple object visual tracking

    … linking," a class of offline batch processing algorithms for long-term occlusions, where the decision has to be made based on the observations from the entire tracking sequence. We construct a graph representation to characterize occlusion events and propose an efficient …

    bu Repository record for Occlusion reasoning for multiple object visual tracking (opens in a new tab)

  17. Robust stabilization of interconnected systems by means of structurally constrained controllers

    … into a number of bipartite graphs. A simple combinatorial algorithm is subsequently proposed to address the problem under consideration. The second problem investigated here is the characterization of all classes of LTI structurally constrained controllers with respect to which a given …

    concordia Download PDF for Robust stabilization of interconnected systems by means of structurally constrained controllers (opens in a new tab)

  18. Dynamic Resource Allocation in Wireless Heterogeneous Networks

    … novel and efficient dynamic resource allocation algorithms in the frequency, time and space domains. We show that the proposed algorithms perform better than the current state-of-art resource management algorithms. In the first part of the dissertation, we propose an interference management …

    maryland Repository record for Dynamic Resource Allocation in Wireless Heterogeneous Networks (opens in a new tab)

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

    … 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 critical special case of the metric …

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

  20. A Collapsing Method for Efficient Recovery of Optimal Edges

    In this thesis we present a novel algorithm, <I>HyperCleaning*</I>, for effectively inferring phylogenetic trees. The method is based on the quartet method paradigm and is guaranteed to recover the best supported edges of the underlying phylogeny based on the witness quartet set. This is performed …

    waterloo Repository record for A Collapsing Method for Efficient Recovery of Optimal Edges (opens in a new tab)

Page 1 of 2