Lawrence V. Snyder · RePEc: Research Papers in Economics
Abstract The mail-order DVD rental company Netflix chooses distribution center locations so that most of its customers receive their DVDs within one business day via first-class U.S. Mail. Similarly, many municipalities aim to have fire crews reach 911 callers within a specified time, such as four minutes. Both of these are examples of the notion of coverage, a concept central to several classes of facility location models; it indicates whether a demand location is within a pre-specified radius (measured by distance, travel time, cost, or another metric) of its assigned facility. Homeowners are covered if they are within four minutes of the nearest fire station, and Netflix customers are covered if they are within one mailing day of a distribution center. Note that in the fire-station example, municipalities typically want to cover all residents (while minimizing the number of service stations to open), whereas Netflix wants to cover as many customers as possible (subject to a limit on the number of warehouses it may operate at any time, as specified by its capital budget). The fire-station problem is an example of the set covering location problem (SCLP), while Netflix’s problem is an example of the maximal covering location problem (MCLP). This chapter discusses both problems.
Cited by 0
Douglas R. Shier · 1991
Abstract This chapter studies a type of reliability problem in which a given set S needs to be covered by certain of its subsets. The subsets are available for use on a random and independent basis with known probabilities. It is of interest to calculate the probability that the entire set S is ‘covered’ by the operating subsets: i.e., every element of Sis present in some available subset. As an example of such a problem, consider a mass transit system containing a number of bus routes and the stops they serve. Because of maintenance or staffing problems, a particular bus route might not always be in service: specifically the route is only known to operate (or be available) with some fixed probability. A useful performance measure for the transit system is therefore the probability that each stop is served by some operating bus route. There are a number of other possible applications of this model, such as evaluating the reliability of delivery routes (needed to cover customer demands) or determining the reliability of flight schedules for aircraft (serving airports). Another application is discussed more fully in Section 7.1, and a general description of the reliability covering problem is presented in Section 7.2. It is shown that solving the covering problem is, in fact, equivalent to calculating the reliability of a coherent system, which is known to be mathematically difficult. Consequently, the general covering problem is provably hard.
Cited by 0
David Avis · 1980
Cited by 43
Lint, JH van · TU/e Research Portal (Eindhoven University of Technology) · 1988
Cited by 0
Sergio García, Alfredo Marı́n · Location Science · 2019
Cited by 17
Ronald E. Prather · 1983
Cited by 0
den Bakker, Yvonne (author) · Research Repository (Delft University of Technology) · 2021
Cited by 0Open access
Gentle, Amber Estelle · Figshare · 2024
Sequence covering arrays are a mathematical object employed in many software testing schemes as they allow for sequences of events of a fixed length to be tested at least once each. A recently introduced variant called the perfect sequence covering array imposes that each sequence be covered the same number of times. In this thesis, we address problems concerning these objects, including finding minimal examples of perfect sequence covering arrays and presenting a general method of construction for perfect sequence covering arrays.
Cited by 0Open access
Richard Church, John Current · RePEc: Research Papers in Economics
Hutson and ReVelle [8] define the maximal direct covering tree problem as a bicriterion problem to identify a subtree of a given tree. The two criteria are to maximize demand covered by the subtree and to minimize the cost of the subtree. Demand at a node on the underlying tree is considered covered if it is within some prespecified covering distance S of the subtree. In the direct covering version of the problem. S = 0. In this article we present a new bicriterion formulation of the maximal direct covering tree problem and present O(n2) algorithms for solving both this problem and the special case where one must add to an existing subtree. The new formulation is extremely concise; consequently, additional constraints may be added where appropriate. This is demonstrated with the addition of a budget constraint. In addition, we demonstrate that the new formulation and algorithm can be readily extended to incorporate indirect covering (i.e., S > 0) as defined by Kim et al. [9]. © 1993 John Wiley & Sons. Inc.
Cited by 0
Éric Angel, Evripidis Bampis, Vincent Chau et al. · Lecture notes in computer science · 2015
Cited by 9
Henna Koivusalo, Lingmin Liao, Tomas Persson · International Mathematics Research Notices · 2021
Abstract Motivated by the random covering problem and the study of Dirichlet uniform approximable numbers, we investigate the uniform random covering problem. Precisely, consider an i.i.d. sequence $\omega =(\omega _n)_{n\geq 1}$ uniformly distributed on the unit circle $\mathbb{T}$ and a sequence $(r_n)_{n\geq 1}$ of positive real numbers with limit $0$. We investigate the size of the random set $$\begin{align*} & {\operatorname{{{\mathcal{U}}}}} (\omega):=\{y\in \mathbb{T}: \ \forall N\gg 1, \ \exists n \leq N, \ \text{s.t.} \ | \omega_n -y | < r_N \}. \end{align*}$$Some sufficient conditions for ${\operatorname{{{\mathcal{U}}}}}(\omega )$ to be almost surely the whole space, of full Lebesgue measure, or countable, are given. In the case that ${\operatorname{{{\mathcal{U}}}}}(\omega )$ is a Lebesgue null measure set, we provide some estimations for the upper and lower bounds of Hausdorff dimension.
Cited by 0Open access
Gentle, Amber Estelle · Monash University · 2024
Sequence covering arrays are a mathematical object employed in many software testing schemes as they allow for sequences of events of a fixed length to be tested at least once each. A recently introduced variant called the perfect sequence covering array imposes that each sequence be covered the same number of times. In this thesis, we address problems concerning these objects, including finding minimal examples of perfect sequence covering arrays and presenting a general method of construction for perfect sequence covering arrays.
Cited by 0Open access
Olivier Coudert · 1996
Article Free Access Share on On solving covering problems Author: Olivier Coudert Synopsys Inc., 700 East Middlefield Rd., Mountain View, CA Synopsys Inc., 700 East Middlefield Rd., Mountain View, CAView Profile Authors Info & Claims DAC '96: Proceedings of the 33rd annual Design Automation ConferenceJune 1996 Pages 197–202https://doi.org/10.1145/240518.240555Online:01 June 1996Publication History 87citation747DownloadsMetricsTotal Citations87Total Downloads747Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Cited by 131Open access
Stefan Porschen · International Journal of Computational Geometry & Applications · 2009
Many applications like image processing, data compression or pattern recognition require a covering of a set of n points most often located in the (discrete) plane by rectangles due to specific cost constraints. In this paper we provide exact dynamic programming algorithms for covering point sets by regular rectangles, that have to obey certain boundary conditions, namely all rectangles must have lengths of at least k, which is a prescribed problem parameter. The concrete objective function underlying our optimization problem is the sum of area, circumference and a constant over all rectangles forming a covering. This objective function can be motivated by requirements of numerically solving PDE's by discretization over (adaptive multi-)grids. More precisely, we propose exact deterministic algorithms for such problems based on a (set theoretic) dynamic programming approach yielding a time bound of O(n 2 3 n ). In a second step this bound is (asymptotically) decreased to O(n 6 2 n ) by exploiting some structural features. Finally, a generalization of the problem and its solution methods is discussed for the case of arbitrary (finite) space dimension.
Cited by 1
András Bezdek · OhioLink ETD Center (Ohio Library and Information Network) · 1986
a note ap pears to indicate this.3. Oversize materials (maps, drawings, and charts) are photographed by sec tioning the original, beginning at the upper left hand comer and continu ing from left to right in equal sections with small overlaps.Each oversize page is also filmed as one exposure and is available, for an additional charge, as a standard 35mm slide or in black and white paper format.* 4. Most photographs reproduce acceptably on positive
Cited by 1Open access
Timothy J. Lowe · Encyclopedia of Optimization · 2001
Cited by 0
Olivier Coudert Synopsys, Olivier Coudert · 1996
The set covering problem and the minimum cost assignment problem (respectively known as unate and binate covering problem) arise throughout the logic synthesis flow. This paper investigates the complexity and approximation ratio of two lower bound computation algorithms from both a theoretical and practical point of view. It also presents a new pruning technique that takes advantage of the partitioning. 1 Introduction The (unate or binate) covering problem is a well known intractable problem. It has several important applications in logic synthesis, such as two-level logic minimization, two-level Boolean relation minimization, three-level NAND implementation, state minimization, exact encoding, and DAG covering [10, 6, 2]. Although from the practical point of view people are more interested in low cost heuristic algorithms that produce approximate solutions, solving covering problems exactly is the only way to evaluate the performance of these heuristic algorithms. Moreover, improvi...
Cited by 0
Jurij Mihelič, et al. · 2008
We discuss the connection between facility location problems and covering problems, and present approaches to solving facility location problems by reducing them to covering problems. In particular, we discuss the following NP-hard optimization problems: the set cover and the related set cover facility location problem, the k-center and k-suppliers problem, the dominating set problem, the maximum independent set problem, and the maximum covering problem.
Cited by 0
Hatfield, Carole · Royal Holloway Digital Repository (Royal Holloway University of London) · 1970
Our purpose in these pages will be to develop a broad survey of some problems in covering which have been solved using the methods of convexity. The basic aim has been to show the flexibility of approach which is desirable, and to do this we shall discuss ten particular problems with widely differing methods of solution. The problems to be discussed fall into three main categories. covering a single set by a single set with specified properties, covering a single set by many sets, and covering many sets by a single set. The first chapter is a collection of some necessary preliminary definitions and theorems in convexity. In the second chapter we consider six particular problems of covering a single set by a single set: these include finding the convex covers of certain arcs in two and three dimensions, finding the smallest containing sphere of an n-dimensional set, and establishing properties of particular types of containing set. The final chapter contains problems which fall into the other two categories outlined above, and includes finding a single set to cover an infinite class of sets, and covering one set by a finite class of sets. The last paper considered relates one set (the plane) and a given infinite class of sets: it is included for the sake of completeness and because of the methods of solution involved, but in fact can be considered as a problem in covering only if the latter term is not restricted to mean complete covering by a class of sets. A full list of references to the original papers is given at the end.<p>
Cited by 0Open access
Niklas Jost · ArXiv.org · 2025
Hub Covering Problems arise in various practical domains, such as urban planning, cargo delivery systems, airline networks, telecommunication network design, and e-mobility. The task is to select a set of hubs that enable tours between designated origin-destination pairs while ensuring that any tour includes no more than two hubs and that either the overall tour length or the longest individual edge is kept within prescribed limits. In literature, three primary variants of this problem are distinguished by their specific constraints. Each version exists in a single and multi allocation version, resulting in multiple distinct problem statements. Furthermore, the capacitated versions of these problems introduce additional restrictions on the maximum number of hubs that can be opened. It is currently unclear whether some variants are more complex than others, and no approximation bound is known. In this paper, we establish a hierarchy among these problems, demonstrating that certain variants are indeed special cases of others. For each problem, we either determine the absence of any approximation bound or provide both upper and lower bounds on the approximation guarantee.
Cited by 0Open access