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 60 for “"Polynomial time approximation scheme"”.
-
Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι
… given graph G = (V, E). We present algorithms of polynomial time as well as approximation results on special graph classes. Analytically, in the thesis we study polynomial time algorithms for the densest k-subgraph problem on weighted graphs of maximal degree two, on weighted trees even if the …
-
Price-setting Problems and Matroid Bayesian Online Selection
… and ask how well the seller can do with polynomial-time computation, compared to a seller with unlimited computation but with the same limited distribution information about offers. We show that when the underlying constraints are laminar and the arrival of buyers follows a natural …
-
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 …
-
Parameterized complexity and polynomial-time approximation schemes
… This excludes the possibility of solving them in polynomial time unless P=NP. A number of approaches have been proposed in dealing with NPhard problems, among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to find good enough solutions …
-
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 …
-
Resource assignment algorithms for vehicular clouds
… machines is NP-hard. We then provide a fully polynomial time approximation scheme and a greedy approximation for scheduling a single task. We extend these algorithms to the case of scheduling n tasks. We validate our algorithms through extensive simulations that use synthetically generated …
-
Approximation algorithms for minimum knapsack problem
… one. In this thesis we study several existing approximation algorithms for the minimization version of the problem and propose a scaling based fully polynomial time approximation scheme for the minimum knapsack problem. We compare the performance of this algorithm with existing algorithms. Our …
-
Demand Characterization For Real-Time Cyber-Physical Systems: Algorithms, Analysis, And Applications To Control Systems
… and utilization bounding tools to the real-time community toolbox for the effective deployment of real-time, safety-critical cyber-physical systems. Specifically, this work exploits system dynamics for improved real-time analysis in: software-based short circuit detection, intelligent power …
-
The Complexity of Network Design for s-t Eff ective Resistance
… we use dynamic programming to obtain a fully polynomial time approximation scheme when the input graph is a series-parallel graph. Finally, we propose a greedy algorithm for general graphs in which we add a path at each iteration and we conjecture that the algorithm is a $3.95$-approximation …
-
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 …
-
On a 2-path problem
… graph-based problem to be NP-hard. At the same time, we propose a polynomial-time approximation scheme to handle this problem. Although the worst-case performance of the latter scheme is not fully understood yet, we note that under two mild practical assumptions, the scheme yields the optimal …
-
Combinatorial optimization and decision-making with applications in Computational Sustainability
… dams in the Amazon basin. We propose a fully polynomial-time approximation scheme based on Dynamic Programming (DP) for computing the Pareto frontier within an arbitrarily small error margin on tree-structured networks. We also developed a complementary mixed integer programming (MIP) approach …
-
Αλγόριθμοι ελαχιστοποίησης κατανάλωσης ενέργειας σε ασύρματα δίκτυα
… 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 …
-
Minimum Shared-Power Edge Cut
… removal breaks the barrier. We develop a fully polynomial time approximation scheme (FPTAS) for MSPEC. We give polynomial time algorithms for the special cases where the edge weights are uniform, or the power values are restricted to a bounded set. Although MSPEC is related to network flow and …
-
Behaviorally-Informed Discrete Choice Models in Operations Management
… across customer segments. It develops a Fully Polynomial Time Approximation Scheme (FPTAS) that achieves near-optimal solutions efficiently. The third study introduces a discrete choice model that captures multi-product and multi-unit purchases and provides exact and approximate algorithms for …
-
Performance optimization and energy efficiency of big-data computing workflows
… has a significant impact on workflow completion time, energy consumption, and financial cost if executed in clouds, which remains largely unexplored. This dissertation conducts an in-depth investigation into the properties of moldable jobs and provides an experiment-based validation of the …
-
Scheduling Fork-Join Structures in Parallel Systems
… theory. These results include an Efficient Polynomial Time Approximation Scheme (EPTAS) for scheduling to homogeneous systems, as well as more practical approximations and polynomial time algorithms for further sub-cases. In addition to classifying the problem in regards to approximability, …
-
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 …
Page 1 of 3