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

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

    gatech Repository record for Probabilistic covering problems (opens in a new tab)

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

    waterloo Repository record for Covering Problems via Structural Approaches (opens in a new tab)

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

    waterloo Repository record for Mechanism Design For Covering Problems (opens in a new tab)

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

    uiuc Repository record for Coloring and covering problems on graphs (opens in a new tab)

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

    lethbridge Repository record for Investigations on two classes of covering problems (opens in a new tab)

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

    vt Repository record for Generalized total and partial set covering problems (opens in a new tab)

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

    gatech Repository record for Algorithms for budgeted auctions and multi-agent covering problems (opens in a new tab)

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

    ut-knoxville Repository record for District-neighborhood covering problems : model development and multiobjective solution techniques (opens in a new tab)

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

    waterloo Repository record for Approximation Algorithms for Geometric Covering Problems for Disks and Squares (opens in a new tab)

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

    gatech Repository record for On-line algorithms for bin-covering problems with known item distributions (opens in a new tab)

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

    mcmaster Repository record for Formulations and Exact Solution Methods For a Class of New Continous Covering Problems (opens in a new tab)

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

    liege Repository record for Contributions to combinatorics on words in an abelian context and covering problems in graphs (opens in a new tab) Download PDF for Contributions to combinatorics on words in an abelian context and covering problems in graphs (opens in a new tab)

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

    ucf Repository record for Simulation Of Random Set Covering Problems With Known Optimal Solutions And Explicitly Induced Correlations Amoong Coefficients (opens in a new tab)

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

    uiuc Repository record for Fault covers in reconfigurable VLSI chips (opens in a new tab)

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

    waterloo Repository record for Cover Small Cuts and Flexible Graph Connectivity Problems (opens in a new tab)

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

    gatech Repository record for Optimal partitions for the fast multipole method (opens in a new tab)

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

    wvu Repository record for An Empirical Analysis of an Algorithm for the Budgeted Maximum Vertex Cover Problem in Trees (opens in a new tab)

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

    uiuc Repository record for On the topology of the spaces of coverings (opens in a new tab)

Page 1 of 3