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 16 of 16 for “"Polynomial time approximation scheme (PTAS)"”.

  1. A PTAS for the Uncertain Capacity Knapsack Problem

    … n jobs with weights w1 . . .wn and processing times p1 . . . pn, where our goal is to order the jobs on a single machine so as to maximize the weight of all jobs completing prior to a known common deadline d. In this paper, we study the uncertain capacity knapsack problem (UCKP), a …

    clemson Repository record for A PTAS for the Uncertain Capacity Knapsack Problem (opens in a new tab)

  2. Approximation Algorithms for Geometric Covering Problems for Disks and Squares

    … prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it. In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a …

    waterloo Repository record for Approximation Algorithms for Geometric Covering Problems for Disks and Squares (opens in a new tab)

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

    … solution and also present upper bounds on the approximation ratio of several polynomial time algorithms. In the case where the antennas are connected through a wired backbone network we consider a clustering problem. We present an optimal polynomial time algorithm for the special case when …

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

  4. Algorithms for Multiple Sequences Alignment, Comparison of Trees, and Steiner Trees

    … efficiency of algorithms, and the performance of approximation algorithms are stressed.</p> <p>The most popular approach for comparing a set of sequences is multiple sequence alignment. We show that two popular variants of multiple sequence alignment, multiple alignment with SP-score and tree …

    mcmaster Repository record for Algorithms for Multiple Sequences Alignment, Comparison of Trees, and Steiner Trees (opens in a new tab)

  5. An Approximation Algorithm for Character Compatibility and Fast Quartet-based Phylogenetic Tree Comparison

    … character compatibility (CC) paradigm and give a polynomial time approximation scheme (PTAS) for a variation of the formulation called fractional character compatibility (FCC), which has been proven to be NP-hard. We also present a very simple algorithm called the Ordinal Split Method (OSM) to …

    waterloo Repository record for An Approximation Algorithm for Character Compatibility and Fast Quartet-based Phylogenetic Tree Comparison (opens in a new tab)

  6. Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms

    … design and mathematical analysis of randomized approximation algorithms for the hitting set and b-matching problems in hypergraphs. We present a randomized algorithm for the hitting set problem based on linear programming. The analysis of the randomized algorithm rests upon the probabilistic …

    cau-kiel Repository record for Randomized Approximation for the Matching and Vertex Cover Problem in Hypergraphs: Complexity and Algorithms (opens in a new tab)

  7. Approximation Schemes for Machine Scheduling

    … to a set of machines. The jobs have a processing time and the goal is to minimize the latest finishing time of the jobs. Machine scheduling is well known to be NP-hard and thus there is no polynomial time algorithm for this problem that is guaranteed to find an optimal solution unless P=NP. There …

    cau-kiel Repository record for Approximation Schemes for Machine Scheduling (opens in a new tab)

  8. Multiple sink positioning in sensor networks

    … to some sink node. This can increase network lifetime, reduce the occurrence of errors, and reduce latency. We also study variations of the problem where the sink locations are restricted to be at points of a regular lattice (lattice-based covering set), or at network nodes (graph-based covering …

    concordia Download PDF for Multiple sink positioning in sensor networks (opens in a new tab)

  9. Quadratic maximization under combinatorial constraints and related applications

    … exponentially in the rank of the input, but polynomially in the ambient dimension. Extending these observations, we describe a simpler {approximation} algorithm based on exploring the low-rank space with an [epsilon]-net, drastically improving the dependence on the ambient dimension, implying …

    texas Repository record for Quadratic maximization under combinatorial constraints and related applications (opens in a new tab)

  10. Algorithms and complexity analyses for some combinational optimization problems

    … A job may also have an arbitrary release time before which the preprocessing task is not available to be processed. The main objective in this dissertation is to minimize the total completion time or the makespan. Both the complexity and algorithmic issues of these problems are considered. …

    njit Repository record for Algorithms and complexity analyses for some combinational optimization problems (opens in a new tab)

  11. Approximation in batch and multiprocessor scheduling

    … about scheduling problems where jobs arrive over time. Depending on the problem, we consider the case that each job has a deadline, or the relaxation that the sum of flow times or completion times need to be minimized. Since most of the discussed problems are NP-hard, the goal is to find …

    freiburg-diss Repository record for Approximation in batch and multiprocessor scheduling (opens in a new tab)

  12. 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)

  13. In-Network Processing For Mission-Criticalwireless Networked Sensing And Control: A Real-Time, Efficiency, And Resiliency Perspective

    … of jointly optimizing packet packing and the timeliness of data delivery. We identify the conditions under which the problem is strong NP-hard, and we find that the problem complexity heavily depends on aggregation constraints instead of network and traffic properties. For cases when the …

    wayne-thes Repository record for In-Network Processing For Mission-Criticalwireless Networked Sensing And Control: A Real-Time, Efficiency, And Resiliency Perspective (opens in a new tab)

  14. Optimization and Information Problems in Operations

    … demand rate grows. We propose a deterministic approximation policy (DA policy) and show that DA policy provides an upper bound for the original problem and its induced pricing policy achieves asymptotic optimality as the scale of the problem grows properly. Later we consider a dynamic pricing …

    wustl Repository record for Optimization and Information Problems in Operations (opens in a new tab)

  15. Algorithmic Aspects of Packing Problems

    … a base edge and an additional point, there is a polynomial-time approximation scheme (PTAS) to compute the maximum number of copies of an object that can be packed into the container under translation or rigid motions if the following conditions hold: •The inner angles of the container are …

    fu-berlin Repository record for Algorithmic Aspects of Packing Problems (opens in a new tab)

  16. Improved approximation algorithms for packing and scheduling problems

    This thesis presents approximation algorithms for geometric packing and scheduling problems. First, improved AFPTAS for the Bin Packing Problem (BP) and its generalization, the Variable-sized Bin Packing Problem (VBP), are explained. Our algorithms have to solve the unbounded variant of the …

    cau-kiel Repository record for Improved approximation algorithms for packing and scheduling problems (opens in a new tab)