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 45 for “"covering problems"”.
-
Probabilistic covering problems
This dissertation studies optimization problems that involve probabilistic covering constraints. A probabilistic constraint evaluates and requires that the probability that a set of constraints involving random coefficients with known distributions hold satisfy a minimum requirement. A covering …
-
Covering Problems via Structural Approaches
… 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 gap between real-world instances and the …
-
Mechanism Design For Covering Problems
… work in algorithmic mechanism design on packing problems such as single-item auctions, multi-unit auctions and combinatorial auctions. But, surprisingly, covering problems, also called procurement auctions, have almost been completely unexplored, especially in the multidimensional setting. In …
-
Coloring and covering problems on graphs
… is $K_{m,m,m}$. We also consider analogous problems for circular orderings, where pairs of nonincident edges are separated unless their endpoints alternate. Let $\pi^\circ(G)$ be the number of circular orderings needed to separate all pairs, and let $\pi_f^\circ(G)$ be the fractional …
-
Investigations on two classes of covering problems
Covering problems fall within the broader category of facility location, a branch of combinatorial optimization concerned with the optimal placement of service facilities in some geometric space. This thesis considers two classes of covering problems. The first, Covering with Variable Capacities …
-
Generalized total and partial set covering problems
… with the development of two generalized set covering models. The first model is formulated for the total set covering problem where cost is minimized subject to the constraint that each customer must be served by at least one facility. The second model is constructed for the partial set …
-
Algorithms for budgeted auctions and multi-agent covering problems
… we do an algorithmic study of optimization problems in budgeted auctions, and some well known covering problems in the multi-agent setting. We give new results for the design of approximation algorithms, online algorithms and hardness of approximation for these problems. Along the way we …
-
District-neighborhood covering problems : model development and multiobjective solution techniques
<p>This thesis developes several neighborhood impact location models. The obnoxious characteristics associated with public facilities are discussed, and three basic elements concerned with the minimization of neighborhood impact are introduced and a number of formulations are developed within a …
-
Approximation Algorithms for Geometric Covering Problems for Disks and Squares
Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover. In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points …
-
On-line algorithms for bin-covering problems with known item distributions
… focuses on algorithms solving the on-line Bin-Covering problem, when the items are generated from a known, stationary distribution. We introduce the Prospect Algorithm. The main idea behind the Prospect Algorithm is to use information on the item distribution to estimate how easy it will be to …
-
Formulations and Exact Solution Methods For a Class of New Continous Covering Problems
… exact solution methods for a class of continuous covering location models. The manuscript includes three self-contained studies which are organized as in the following. </p> <p> In the first study, we introduce the planar expropriation problem with non-rigid rectangular facilities which has many …
-
Contributions to combinatorics on words in an abelian context and covering problems in graphs
… in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence …
-
Simulation Of Random Set Covering Problems With Known Optimal Solutions And Explicitly Induced Correlations Amoong Coefficients
… is to devise a procedure to generate random Set Covering Problem (SCP) instances with known optimal solutions and correlated coefficients. The procedure presented in this work can generate a virtually unlimited number of SCP instances with known optimal solutions and realistic characteristics, …
-
Fault covers in reconfigurable VLSI chips
… to replace the defective elements. The fault covering problem is to assign the redundant elements to the defective elements such that the chip will function properly. We studied fault covering problems on special architectures, Random Access Memories and Programmable Logic Arrays, and …
-
Cover Small Cuts and Flexible Graph Connectivity Problems
… of the Cover Small Cuts problem, and cut covering problems on strongly pliable families, a subfamily of pliable families. Pliable set families require that for any two sets A, B in the family, at least two of A-B, B-A, A∪B, A∩B are also in the family. Strongly pliable set families require …
-
Optimal partitions for the fast multipole method
… into cells. Insight from studying lattices and covering problems leads to new, more efficient partitions for the FMM. New partitions are designed to reduce near-field and far-field calculations. Results from simulations show significant computation time reduction with little to no additional …
-
An Empirical Analysis of an Algorithm for the Budgeted Maximum Vertex Cover Problem in Trees
Covering problems are commonly studied in fields such as mathematics, computer science, and engineering. They are also applicable in the real world, e.g., given a city, can we build base-stations such that there is network availability everywhere in the city. However, in the real world, there are …
-
On the topology of the spaces of coverings
The spaces of coverings (SoC) arise from various configuration spaces of the covering problems. We study the topology of these spaces for different domains and covering agents. In particular, we study the SoCs for grid domains and metric trees covered by balls. Characterizations of their topology …
Page 1 of 3