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 26 for “"Polynomial-Time Approximation Algorithm"”.

  1. Information-theoretic multi-robot path planning

    … to improve the sampling performance and time efficiency of planning for anisotropic fields. In this thesis, we cast the planning problem into a stagewise decision-theoretic problem. we adopt Gaussian Process to model spatial phenomena. Maximum entropy criterion and maximum mutual …

    nus Repository record for Information-theoretic multi-robot path planning (opens in a new tab) Download file for Information-theoretic multi-robot path planning (opens in a new tab)

  2. Computational Complexity Of Bi-clustering

    … and complement this result by introducing a polynomial time approximation algorithm for this bi-clustering task. This is the first positive approximation guarantee for bi-clustering algorithms. We also show that bi-clustering with our objective function can be viewed as a generalization of …

    waterloo Repository record for Computational Complexity Of Bi-clustering (opens in a new tab)

  3. An Algorithm for Stable Matching with Approximation up to the Integrality Gap

    … attain that of 4/3 − ε (≈ 1.3333). We present a polynomial-time approximation algorithm with a performance guarantee of (3L − 2)/(2L − 1) where L is the maximum tie length. 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)

  4. EFFICIENT GEOMETRIC ALGORITHMS FOR STOCHASTIC AND CATEGORICAL DATA

    Modern algorithmic frameworks must contend with data that is both massive and inherently uncertain. This dissertation explores efficient geometric algorithms for handling such data across two regimes: temporal evolution and spatial classification. In the first part, we address "temporal …

    maryland Repository record for EFFICIENT GEOMETRIC ALGORITHMS FOR STOCHASTIC AND CATEGORICAL DATA (opens in a new tab)

  5. Interference in wireless mobile networks

    … in two or more dimensions (Buchin 2008) and no polynomial-time approximation algorithm is known. We show how to solve the problem efficiently in settings typical for wireless ad hoc networks. We show that if node positions are represented by a set P of n points selected uniformly and …

    ubc Repository record for Interference in wireless mobile networks (opens in a new tab) Download PDF for Interference in wireless mobile networks (opens in a new tab)

  6. Safe, Scalable, and Complete Motion Planning of Large Teams of Interchangeable Robots

    … of novel, complete, computationally tractable algorithms to control a team of robots and avoid collisions while retaining a notion of optimality. This dissertation begins by presenting a robust decentralized formation control algorithm for control of robots operating in tight proximity to one …

    penn Repository record for Safe, Scalable, and Complete Motion Planning of Large Teams of Interchangeable Robots (opens in a new tab)

  7. Algorithms for Integer Programming and Allocation

    The first part of the thesis contains pseudo-polynomial algorithms for integer linear programs (ILP). When certain parameters of an ILP are fixed, that is, they are treated as constants in the running time, it is possible to obtain algorithms with a running time that is pseudo-polynomial in the …

    cau-kiel Repository record for Algorithms for Integer Programming and Allocation (opens in a new tab)

  8. Generalizations, Extensions, and Applications of the Sequential Knapsack Problem

    … smallest to largest. We present an O(n^2 log n) algorithm that solves SKP and the Bounded Sequential Knapsack Problem (B-SKP) exactly, by exploiting the divisibility property of the constraint. We then adapt this algorithm to provide an approximate solution for the more general Consecutive …

    buffalo Repository record for Generalizations, Extensions, and Applications of the Sequential Knapsack Problem (opens in a new tab)

  9. Approximation, Proof Systems, and Correlations in a Quantum World

    … classes. In the classical setting, the study of approximation algorithms and hardness of approximation is one of the main research areas of theoretical computer science. Yet, little is known regarding approximability in the quantum setting. We first demonstrate a polynomial-time approximation …

    waterloo Repository record for Approximation, Proof Systems, and Correlations in a Quantum World (opens in a new tab)

  10. Decision making under uncertainty

    … functions. We present novel exact or approximate algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations or the probability distributions are continuous. The second problem concerns with the stochastic versions of a …

    maryland Repository record for Decision making under uncertainty (opens in a new tab)

  11. Efficient Algorithms for Coordinated Motion in Shared Spaces

    … systems motivates a number of interesting algorithmic problems. These systems, such as self-driving cars, must contend with far more complex and dynamic environments than factory floor robots of the past. This dissertation seeks to identify optimization problems that are simple enough to …

    maryland Repository record for Efficient Algorithms for Coordinated Motion in Shared Spaces (opens in a new tab)

  12. Matchings and Flows in Hypergraphs

    … generalizing bipartite graphs. First, we give a polynomial time approximation algorithm for the maximum weight matching problem on so-called partitioned hypergraphs, whose approximation factor is best possible up to a constant. Afterwards, we look at the theorems of König and Hall and their …

    fu-berlin Repository record for Matchings and Flows in Hypergraphs (opens in a new tab)

  13. Optimization algorithm design and performance analysis for next-generation wireless networks

    … deals with the design of efficient optimization algorithms for next-generation wireless networks, including terrestrial as well as satellite communication systems. More specifically, the theory of sequential convex optimization (SCO) is applied to solve challenging optimization problems, such as …

    greece Repository record for Optimization algorithm design and performance analysis for next-generation wireless networks (opens in a new tab)

  14. A structural approach to matching problems with preferences

    … or all of the agents. We present a number of new algorithmic results for five specific problem domains. Each of these results is derived with the aid of some structural properties implicitly embedded in the problem. We begin by describing an approximation algorithm for the problem of finding a …

    glasgow Download PDF for A structural approach to matching problems with preferences (opens in a new tab)

  15. Σχεδόν βέλτιστοι αλγόριθμοι και αποτελέσματα μη-προσέγγισης για προβλήματα κάλυψης πολυγωνικών περιοχών

    … and studied, regarding its combinatorial and algorithmic aspects. A reasonable variation is to try to cover as many points as possible using a given number of stations. This variation takes into account that a given budget might not suffice for the total covering of the geographical region. …

    greece Repository record for Σχεδόν βέλτιστοι αλγόριθμοι και αποτελέσματα μη-προσέγγισης για προβλήματα κάλυψης πολυγωνικών περιοχών (opens in a new tab)

  16. Approximation algorithms for multidimensional bin packing

    … bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the early seventies. In the classical bin packing problem, we are given a list of real numbers in the range (0, 1], the goal is to place them in a minimum number of bins so that …

    gatech Repository record for Approximation algorithms for multidimensional bin packing (opens in a new tab)

  17. RESOURCE MANAGEMENT FOR MOBILE COMPUTATION OFFLOADING

    … remote task execution, so that task completion time constraints are satisfied. The objective is to minimize the average power consumption of the MDs, subject to a cost budget constraint on communication and computation resources. The thesis includes contributions for both soft and hard task …

    mcmaster Repository record for RESOURCE MANAGEMENT FOR MOBILE COMPUTATION OFFLOADING (opens in a new tab)

  18. Προσεγγιστικοί αλγόριθμοι για δρομολόγηση πακέτων μηνυμάτων σε δίκτυα με κόστος επανεκκίνησης

    … applications as far as Optical Networks, TDMA (Time Division Multiple Access) and parallel message or data transmission are concerned. For the purposes of this manuscript the graph theoretic model of the problem is used. Researchers are referring to the problem at hand as PREEMPTIVE BIPARTITE …

    greece Repository record for Προσεγγιστικοί αλγόριθμοι για δρομολόγηση πακέτων μηνυμάτων σε δίκτυα με κόστος επανεκκίνησης (opens in a new tab)

  19. View Selection for Large Scale 3D Reconstruction

    … indoor cleaning to transportation. Systems and algorithms are being developed at a rapid pace to capture the markets driving these applications. Capturing data to visualize and understand the operating environments in these applications is crucial. Whether it is to capture a High-Definition (HD) …

    umn Repository record for View Selection for Large Scale 3D Reconstruction (opens in a new tab)

  20. Environmental Monitoring with Unmanned Aerial Vehicles

    … and accuracy. Data collection is important for algorithms and systems that try to learn how the physical world works or try to interact with it. The number, variety and quality of the data directly affects the performance of these algorithms. In order to fully realize this vision we need to …

    umn Repository record for Environmental Monitoring with Unmanned Aerial Vehicles (opens in a new tab)

Page 1 of 2