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"”.

  1. 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 …

    waterloo Repository record for NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials (opens in a new tab)

  2. 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 …

    iastate Repository record for On minimal support solutions of underdetermined systems of linear equations (opens in a new tab)

  3. 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, …

    waterloo Repository record for On the Hardness of the Quantum Separability Problem and the Global Power of Locally Invariant Unitary Operations (opens in a new tab)

  4. Αλγόριθμοι ελαχιστοποίησης κατανάλωσης ενέργειας σε ασύρματα δίκτυα

    … 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 …

    greece Repository record for Αλγόριθμοι ελαχιστοποίησης κατανάλωσης ενέργειας σε ασύρματα δίκτυα (opens in a new tab)

  5. 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 …

    uiuc Repository record for Choice modeling and recommendation optimization in presence of context effects (opens in a new tab)

  6. 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 …

    sask Repository record for Maximum Clique in Geometric Intersection Graphs (opens in a new tab)

  7. 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.

    waterloo Repository record for Craniosynostosis Surgery: A Study of Rearrangement (opens in a new tab)

  8. 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 …

    waterloo Repository record for Computing Realistic Terrains from Imprecise Elevations (opens in a new tab)

  9. 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 …

    uiuc Repository record for Visibility analysis of landmark-based navigation (opens in a new tab)

  10. 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 …

    gatech Repository record for Theoretical Results and Applications Related to Dimension Reduction (opens in a new tab)

  11. 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 …

    aalto Repository record for On the connectivity interdiction problem, the geometry of data structures and Eulerian circuits (opens in a new tab)

  12. 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 …

    texas Repository record for Learning with latent structures, robustness and non-linearity : non-convex approaches (opens in a new tab)

  13. 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 …

    birmingham Download PDF for Integrality in max-linear systems (opens in a new tab)

  14. 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 …

    oxford Repository record for Angle and distance geometry problems (opens in a new tab)

  15. 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 …

    oxford Repository record for Promise constraint satisfaction problems (opens in a new tab)

  16. 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 …

    texas-state Repository record for A Massively Parallel Exact TSP Solver for Small Problem Sizes (opens in a new tab)

  17. 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 …

    ubc Repository record for Inventory management optimization : a case study of Amazon supply chain (opens in a new tab) Download PDF for Inventory management optimization : a case study of Amazon supply chain (opens in a new tab)

  18. 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 …

    tamu Repository record for On Covering Points with Conics and Strips in the Plane (opens in a new tab)

Page 1 of 6