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)"”.
-
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 …
-
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 …
-
Αλγόριθμοι ελαχιστοποίησης κατανάλωσης ενέργειας σε ασύρματα δίκτυα
… 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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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. …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …