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 14 of 14 for “"apx-hard"”.
-
Computational and communication complexity of geometric problems
… For the sequential setting, we prove the first hardness of approximation results for the following problems: \begin{itemize} \item Red-Blue Geometric Set Cover is APX-hard when the objects are axis-aligned rectangles. \item Red-Blue Geometric Set Cover cannot be approximated to within …
-
Introduction to the Minimum Rainbow Subgraph problem
… exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we …
-
Implementation and Performance Comparison of Some Heuristic Algorithms for Block Sorting
… been developed in this thesis for a well-known APX-hard combinatorial optimization problem known as Block Sorting. The motivation for the study of this problem comes from applications such as computational biology and optical character recognition. While existing Block Sorting research has been …
-
The Traveling Tournament Problem
… the problem. Despite existing results on the NP-hardness of TTP, the question of whether or not TTP is also APX-hard was an unexplored area in the literature. We prove the affirmative by constructing an L-reduction from (1,2)-TSP to TTP. To reach the desired result, we show that given an instance …
-
Study of two biochemical models : chemical reaction networks, and nucleic acid systems
… base pairs). We show that this problem is APX-hard which implies that there does not exist a polynomial time approximation scheme for this problem, unless P = NP. We also propose a new Monte-Carlo based method to efficiently estimate nucleic acid folding kinetics.
-
Parallel Algorithms For Steiner Forest
… pairs together. The Steiner Forest Problem is APX-hard and NP-hard to approximate within 96/95. Several heuristic and approximation algorithms, with different approximation guarantees, have been proposed for the Steiner Forest Problem. Despite the several research in designing sequential and …
-
Approximation in batch and multiprocessor scheduling
… Since most of the discussed problems are NP-hard, the goal is to find polynomial time algorithms with provable approximation guarantee, preferably in an on-line setting. <br> <br>In the first part of this thesis, we consider batch scheduling problems for the case that each job has a deadline, …
-
Stabbing and Covering Geometric Objects in the Plane
… deciding the existence of a convex stabber is NP-hard for many types of geometric objects. Additionally, we consider an optimization version and prove it to be APX-hard for most of the considered objects. A similar problem is deciding whether geometric objects can be stabbed with the vertices of a …
-
Solving product-mix markets and learning agents’ preferences
… used in practice. It presents algorithms and hardness results for solving these auctions with the goal of maximising social welfare or revenue, and develops procedures to facilitate participating agents in expressing their preferences in the auction's bidding language.</p> <p>The …
-
Σχεδόν βέλτιστοι αλγόριθμοι και αποτελέσματα μη-προσέγγισης για προβλήματα κάλυψης πολυγωνικών περιοχών
… the calculation of the function value is NP-hard and the cases where there are fixed costs in order to place guards and the total cost has to be within a given budget. For all these variations we prove that we have NP-hard problems and by applying the proposed greedy approach, we construct …
-
Algorithmic aspects of fixed-size coalition formation
… problems associated with 3DR are typically hard, we consider approximate solutions and restricted cases, with the aim of characterising the boundary between tractable and intractable variants. Part of our contribution relates to two new models of 3DR, which involve two existing systems of …
-
Algorithms for Networks With Uncertainty
… remaining graph. We show that this problem is APX-hard, and obtain a $3/2$-approximation algorithm. We additionally introduce symmetric interdiction as a general model.</p><p> We give a general framework that relates optimization to symmetric interdiction for a broad class of optimization …
-
Clustering, weighted sequences, and shortest paths
… classification. Both problems were known to be APX-Hard and the best known approximation factor was O((logn)(loglogn)) by Ailon and Charikar [FOCS '05]. We design asymptotically optimal constant factor approximations for both problems. Our paper "Fitting Distances by Tree Metrics Minimizing the …
-
Covering Problems via Structural Approaches
… problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many …