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 69 for “"Set cover"”.
-
Survey of Approximation Algorithms for Set Cover Problem
… 11 approximation algorithms for unweighted set cover problem. I have also implemented the three algorithms and created a software library that stores the code I have written. The algorithms I survey are: 1. Johnson's standard greedy; 2. f-frequency greedy; 3. Goldsmidt, Hochbaum and Yu's …
-
Geometric set cover and related geometric optimization problems
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-03-01 without embargo terms
-
Fort Neighborhoods: A Set Cover Formulation for Power Domination
… domination numbers and minimum power dominating sets in graphs. Additionally, it shows how the existence of solutions of special forms can be exploited by computational methods. Power domination studies arise from a key problem in electrical engineering concerning placements of monitoring devices …
-
Προσεγγιστικοί αλγόριθμοι για το Generalized Min-Sum Set Cover
… για το πρόβλημα Generalized Min-Sum Set Cover ή Multiple Intents Re-Ranking, Σε αυτό το NP-hard πρόβλημα, μας δίνεται μια συλλογή από σύνολα. Το κάθε σύνολο S έχει μια απαραίτητη προϋπόθεση κάλυψης K(S). Στόχος είναι να διατάξουμε τα στοιχεία των συνόλων σε τέτοια σειρά ώστε ο μέσος …
-
Finding the minimum illuminating direction set for a polyhedron
<p>The minimum illuminating direction set cover problem for a polyhedron seeks the minimum cardinality set of 3-D directions that illuminate the entire polyhedron surface. This thesis introduces a new algorithm for solving such problem. The algorithm includes four steps: (1) Computing sliding …
-
Covering Problems via Structural Approaches
The minimum set cover problem is, without question, among the most ubiquitous and well-studied 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 …
-
Design and Evaluation of New Search Paradigms and Power Management for Peer-to-Peer File Sharing
… is studied as an application of the minimum set cover problem. A reduction in overall energy consumption is achieved by powering down hosts that have all of their shared files fully shared (or covered) by other hosts. A new set cover heuristic -- called the Random Map Out (RMO) algorithm --is …
-
Quantum Annealing for Solving Optimization Problems
… theoretical and practical importance. One is the Set Cover with Pairs problem. The other is the Factorization problem. The Set Cover with Pairs (SCP) problem is a generalization of the Set Cover problem. It requires each element in a set to be covered by at least two objects instead of one as in …
-
Essays on Labor Economics
… theoretical and practical importance. One is the Set Cover with Pairs problem. The other is the Factorization problem. The Set Cover with Pairs (SCP) problem is a generalization of the Set Cover problem. It requires each element in a set to be covered by at least two objects instead of one as in …
-
Sparsity-Driven Search for Multi-Hit Genetic Mutation Combinations in Cancer
… for candidate combinations used by weighted set cover - which is grounded in a depth-first search backtracking technique, prunes infeasible gene subsets early, while a standard greedy weighted set cover (WSC) formulation systematically scores and selects the most discriminative combinations. …
-
Algorithms for NP-hard Optimization Problems and Cluster Analysis
The set cover problem, weighted set cover problem, minimum dominating set problem and minimum weighted dominating set problem are all classical NP-hard optimization problems of great importance in both theory and real applications. Since the exact algorithms, which require exhaustive exploration of …
-
Online Allocation with Concave and Convex Objectives
… for a wider variety of objectives and problem settings. The results of this thesis are presented in two parts: In Part I, we examine online maximization problems, including matching and resource allocation, while in Part II, we examine online minimization problems, including load balancing, …
-
Computational and communication complexity of geometric problems
… a number of geometric problems in different settings. We present lower bounds and approximation algorithms for geometric problems in sequential and distributed settings. For the sequential setting, we prove the first hardness of approximation results for the following problems: …
-
Data-driven Optimization for Low-Power Wide-Area Network Planning
… tools, optimization methods, and the mindset of data-driven decision-making, to develop a toolkit for planning and operating LPWANS in a principled approach. First, we formulate learnable models for both wireless connectivity and interference. Our work on interference features a new …
-
Hybridní kvantové počítání: praktické využití a implementace
… uplatnitelných optimalizačních úloh jako Exact Set Cover, Knapsack, SAT na kvantových počítačích. Na rozdíl od klasických počítačů, které pracují s bity, využívají kvantové počítače kvantové qubity a jevy jako superpozice a provázanost, což jim umožňuje paralelně prohledávat rozsáhlé stavové …
-
Stabilizing Column Generation via Dual Optimal Inequalities with Applications in Logistics and Robotics
… novel classes of DOI for the general context of set cover problems. We refer to these as Smooth DOI (S-DOI) and Flexible DOI (F-DOI). S-DOI can be interpreted as allowing for the undercovering of items at the cost of overcovering others and incurring an objective penalty. SDOI leverage the fact …
-
Cross-monotonic Cost-Sharing Methods for Network Design Games
… cost-sharing methods. That is, for a given set of players and their connection requirements, our algorithms compute a solution that satisfies all the players’ requirements and calculates ’fair’ prices to charge each of them for the connection. Our cost-sharing methods use a primal-dual …
-
Estimating Genotype-Tissue Specific Gene Expression Via Promoter Motifs, Genomic Proximity, And Hybrid Deep Learning
… estimate genome-wide expression from a minimal set of reference genes. We formulate reference gene selection as a set-cover problem and develop a dynamic programming based vicinity set cover algorithm that identifies an optimal and compact reference set while minimizing distances between …
-
Design analytics for product family optimization
… I propose a new method that finds a finite subset of the solution space. The method formulates the problem as optimization problems and utilizes a derivative-free method. With the design sample that is collected from the solution space, a mixed integer linear programs are built and solved …
-
Approximation algorithms for guarding 1.5 dimensional terrains
… chain (the terrain) and asks for the minimum set of vertices of the terrain (guards) such that every vertex of the terrain is seen by at least one guard. This terrain guarding problem is a restriction of the SET COVER problem, which is known to be both NP-complete and inapproximable within a …
Page 1 of 4