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 120 for “"NP-hardness"”.
-
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
… answer to the question by showing that it is NP-hard over any field. Sparse orbit complexity of a polynomial f is the smallest integer s_0 such that there exists an invertible transform A such that f(Ax) has s_0 monomials. Since ETsparse is NP-hard hence computing the sparse orbit complexity …
-
On minimal support solutions of underdetermined systems of linear equations
… for finding minimal support solutions. The NP-Hardness of minimal-support solution recovery is then demonstrated over any field for the first time in the literature, and further NP-Hardness results are explored after this presentation. Following these expositions, a summary of current …
-
On the Hardness of the Quantum Separability Problem and the Global Power of Locally Invariant Unitary Operations
… this thesis, we first strengthen Gurvits’ 2003 NP-hardness result for QUSEP by showing that the Weak Membership problem over the set of separable bipartite quantum states is strongly NP-hard, meaning it is NP-hard even when the error margin is as large as inverse polynomial in the dimension, …
-
Αλγόριθμοι ελαχιστοποίησης κατανάλωσης ενέργειας σε ασύρματα δίκτυα
… energy levels. We prove results concerning the NP hardness of computing the optimal solution or in some cases even an approximate 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 …
-
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 …
-
Craniosynostosis Surgery: A Study of Rearrangement
… of cranial vault remodeling surgery, and prove NP-hardness for our formulation. We then provide several heuristics and test their performance in an experimental study.
-
Computing Realistic Terrains from Imprecise Elevations
… surface area. We give algorithms in some cases, hardness results in other cases. Specifically, we consider four objectives: (1) minimizing the number of local extrema; (2) optimizing coplanar features; (3) minimizing the surface area; (4) minimizing the maximum steepness. Problem (1) is known 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 …
-
A fast heuristic for finding the minimum weight triangulation
… time, or that can be used to prove the NP-Hardness of the MWT problem.
-
Theoretical Results and Applications Related to Dimension Reduction
… discussed. The second project introduces the NP-hardness problem for penalized likelihood estimators, including penalized least squares estimators, penalized least absolute deviation regression and penalized support vector machines. The third project focuses on the application of manifold …
-
On the connectivity interdiction problem, the geometry of data structures and Eulerian circuits
… and theoretical and structural barriers like NP-hardness. In order to by-pass some of the theoretical barriers, this thesis explores several graph and optimization problems through approximation algorithms, data structures, extremal combinatorics and geometry, establishing new state-of-the-art …
-
Learning with latent structures, robustness and non-linearity : non-convex approaches
… some learning problems, which typically involve NP-hardness in the worst case, can be solved in polynomial time. This thesis seeks to tackle these challenges for a few statistical learning problems: mixed linear regression, robust principal component analysis, single index models in both standard …
-
Integrality in max-linear systems
… begins with the one-sided systems and the subeigenproblem. The description of all integer solutions to each of these systems can be achieved in strongly polynomial time. The main max-linear systems that we consider include the eigenproblem, and the problem of determining whether a matrix has an …
-
Angle and distance geometry problems
… are possible. I show that both DGP and ADGP are NP-hard, but that in some sense the ADGP is more expressive than the DGP. To combat the problems of NP-hardness I present some graph theoretic heuristics which may be applied to both DGP and ADGP, and so reduce the time required by general purpose …
-
Promise constraint satisfaction problems
… from those that are not even 1-satisfiable is NP-hard if g/k < 1/2 and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus we give a dichotomy for a natural fragment of …
-
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 …
-
Inventory management optimization : a case study of Amazon supply chain
… stages using a Greedy algorithm to address the NP-hardness of the problem. We develop a theoretical bound on the optimality gap caused by aggregation method. The numerical examples demonstrate that the large-scale algorithm is a computationally efficient approach which produce low-cost solutions …
-
On Covering Points with Conics and Strips in the Plane
… bounded by dimension d. Line cover is NP-hard, so is its hyperplane analogue. Our thesis focuses on few extensions of hyperplane cover and line cover. One of the techniques used to study NP-hard problems is Fixed Parameter Tractability (FPT), where, in addition to input size, a …
Page 1 of 6