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 29 for “"NP-hardness"”.
-
On basing private information retrieval on NP-hardness
… objects on the (minimal) assumption that NP ... BPP is at the very heart of complexity-theoretic cryptography. Most known results along these lines are negative, showing that assuming widely believed complexity-theoretic conjectures, there are no reductions from an NP-hard problem to the …
-
On the hardness of the shortest vector problem
… it. We prove that the shortest vector problem is NP-hard (for randomized reductions) to approximate within some constant factor greater than 1 in any 1, norm (p >\=1). In particular, we prove the NP-hardness of approximating SVP in the Euclidean norm 12 within any factor less than [square root …
-
On approximating projection games
… a problem of great significance in the field of hardness of approximation since almost all NP-hardness of approximation results known today are derived from the NP-hardness of approximation of projection games. Hence, it is important to determine the exact approximation ratio at which projection …
-
Choice modeling and recommendation optimization in presence of context effects
… effects in different settings with different input data structures. For these settings, we also study combinatorial problems concerned with finding the optimal set of products to offer to the customer including (i) assortment optimization problem or reward maximization problem, (ii) click …
-
Maximum Clique in Geometric Intersection Graphs
… labelling. This method is used to show the NP- hardness of finding a maximum clique in various geometric intersection graphs, acting as a way to augment the commonly used co-2-subdivision approach. Finally, finding maximum clique in two classes of geometric intersection graphs are proven to …
-
Visibility analysis of landmark-based navigation
… required to ensure that every point in an input polygon sees at least one landmark but sees no more than one landmark of any particular class. The problem is motivated by partially distinguishable landmark-based navigation. A robot that navigates by landmarks must ensure that it always has …
-
Below P vs NP : fine-grained hardness for big data problems
The theory of NP-hardness has been remarkably successful in identifying problems that are unlikely to be solvable in polynomial time. However, many other important problems do have polynomial-time algorithms, but large exponents in their runtime bounds can make them inefficient in practice. For …
-
A Massively Parallel Exact TSP Solver for Small Problem Sizes
… important real-life applications, but its NP-hardness makes it difficult to find an optimal solution even for relatively small problem sizes. The literature describes many heuristic algorithms that solve the problem approximately but only few exact algorithms. The TSP solver implemented in …
-
From String to Structure: Graph Threading for Physical Assembly
… characterize the complexity landscape, proving NP-hardness for graphs of maximum degree 4, tractability for degree 3, and giving exact and approximation algorithms for restricted variants, including rectangular grid graphs. Finally, we turn from theory to fabrication, proposing …
-
Consensus Algorithms for Trees and Strings
… on lowest common ancestor relations. Our NP-hardness proofs, polynomial-time approximation algorithms, and polynomial-time exact algorithms indicate that these problems become computationally easier if the resulting tree is required to comply with a prespecified left-to-right ordering of …
-
Topics in applied topology
… dimensional observations. We then establish the NP-hardness of decomposing a density function into a minimal number of unimodal components, an important problem in topological statistics, and extend these results to higher-dimensional simplicial complexes.
-
Approximation algorithms for resource allocation optimization.
… a key challenge, since these problems are NP-hard. For all the resource allocation problems studied in this thesis, we are given a set of sites containing facilities as resources, a set of clients to access these facilities, an opening cost for each facility, and a connection cost for each …
-
Bottleneck-based heuristic for permutation flowshop scheduling
… with large number of machine, m > 2, it is NP-hardness. Thus, the main objective of this study are to propose and develop a new heuristic for solving permutation flowshop scheduling by considering four-machines and n-jobs (n = 6, 10, 15, 20). Three phases were applied into this study in …
-
Resource management in wireless heterogeneous networks: an optimization perspective
… resulting optimization problem. We establish the NP-hardness of this problem for a wide range of system-wide utility functions.Due to the fundamental difficulty of globally solving these problems, our emphasis in the rest of this dissertation is on devising efficient algorithms that can …
-
Simulated annealing algorithm for customer-centric location routing problem
… limitation on the size of the problem due to the NP-hardness of the LRP. Therefore, we introduce three different variations of Simulated Annealing (SA) algorithm to solve the Capacitated Latency Location Routing Problem (CLLRP). According to the comparison results on a popular benchmark test, one …
-
Algorithms and hardness results for the jump number problem, the joint replenishment problem, and the optimal clustering of frequency-constrained maintenance jobs
… numbers. We use this connection to derive hardness results for three different problems: -- The Joint Replenishment Problem with General Integer Policies. -- The Joint Replenishment Problem with Correction Factor. -- The Problem of Optimal Clustering of Frequency-Constrained Maintenance …
-
Closed quasigeodesics, escaping from polygons, and conflict-free graph coloring
… approximation scheme. Finally, we prove NP-hardness and hardness of approximation results for related problems with multiple zombies and/or humans. Conflict-free graph coloring. A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for …
-
Security Games: Solution Concepts and Algorithms
… security game model in polynomial time and prove NP-hardness of solving other variants of the model. We also extend the family of security games by allowing the attacker have multiple resources. We provide an algorithm for computing an NE of such games in polynomial time, and we show that …
-
An approach to robustness in stable marriage and stable roommates problems
… (RSM). Subsequently, we prove that RSM is NP-hard, and the decision problem for the case where a=1 (i.e. deciding if there exists a (1,b)-supermatch) is NP-complete. We also develop a constraint programming model and a number of meta-heuristic approaches to find a (1,b)-supermatch that …
-
Conformance preserving data dissemination for large-scale peer to peer systems
… optimality of our approach. We further prove the NP-hardness of the filter overlay construction and give a O(ln n)-approximation algorithm to minimize the level-wise communication cost. We extend the model to support a richer and more expressive subscription semantics, allowing the user interest …
Page 1 of 2