Covering problems

Last updated January 22, 2025

In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems and usually integer linear programs, whose dual problems are called packing problems.

General linear programming formulation

In the context of linear programming, one can think of any minimization linear program as a covering problem if the coefficients in the constraint matrix, the objective function, and right-hand side are nonnegative.^[1] More precisely, consider the following general integer linear program:

minimize	$\sum _{i=1}^{n}c_{i}x_{i}$
subject to	$\sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ for }}j=1,\dots ,m$
	$x_{i}\in \left\{0,1,2,\ldots \right\}{\text{ for }}i=1,\dots ,n$ .

Such an integer linear program is called a covering problem if $a_{ji},b_{j},c_{i}\geq 0$ for all $i=1,\dots ,n$ and $j=1,\dots ,m$ .

Intuition: Assume having $n$ types of object and each object of type $i$ has an associated cost of $c_{i}$ . The number $x_{i}$ indicates how many objects of type $i$ we buy. If the constraints $A\mathbf {x} \geq \mathbf {b}$ are satisfied, it is said that $\mathbf {x}$ is a covering (the structures that are covered depend on the combinatorial context). Finally, an optimal solution to the above integer linear program is a covering of minimal cost.

Kinds of covering problems

There are various kinds of covering problems in graph theory, computational geometry and more; see Category:Covering problems. Other stochastic related versions of the problem can be found.^[2]

The disk covering problem, which asks what the smallest real number
r
(
n
)
{\displaystyle r(n)}
is such that
n
{\displaystyle n}
disks of radius
r
(
n
)
{\displaystyle r(n)}
can be arranged in such a way as to cover the unit disk. DiscCoveringExample.svg — The disk covering problem, which asks what the smallest real number $r(n)$ is such that $n$ disks of radius $r(n)$ can be arranged in such a way as to cover the unit disk.

Covering in Petri nets

For Petri nets, the covering problem is defined as the question if for a given marking, there exists a run of the net, such that some larger (or equal) marking can be reached. Larger means here that all components are at least as large as the ones of the given marking and at least one is properly larger.

Rainbow covering

In some covering problems, the covering should satisfy some additional requirements. In particular, in the rainbow covering problem, each of the original objects has a "color", and it is required that the covering contains exactly one (or at most one) object of each color. Rainbow covering was studied e.g. for covering points by intervals:^[5]

There is a set J of n colored intervals on the real line, and a set P of points on the real line.
A subset Q of J is called a rainbow set if it contains at most a single interval of each color.
A set of intervals J is called a covering of P if each point in P is contained in at least one interval of Q.
The Rainbow covering problem is the problem of finding a rainbow set Q that is a covering of P.

The problem is NP-hard (by reduction from linear SAT).

Conflict-free covering

A more general notion is conflict-free covering.^[6] In this problem:

There is a set O of m objects, and a conflict-graph G_O on O.
A subset Q of O is called conflict-free if it is an independent set in G_O, that is, no two objects in Q are connected by an edge in G_O.
A rainbow set is a conflict-free set in the special case in which G_O is made of disjoint cliques, where each clique represents a color.

Conflict-free set cover is the problem of finding a conflict-free subset of O that is a covering of P. Banik, Panolan, Raman, Sahlot and Saurabh^[7] prove the following for the special case in which the conflict-graph has bounded arboricity:

If the geometric cover problem is fixed-parameter tractable (FPT), then the conflict-free geometric cover problem is FPT.
If the geometric cover problem admits an r-approximation algorithm, then the conflict-free geometric cover problem admits a similar approximation algorithm in FPT time.

Related Research Articles

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

In geometry and group theory, a lattice in the real coordinate space $is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension which spans the vector space . For any basis of, the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a regular tiling of a space by a primitive cell.$

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

<span class="mw-page-title-main">Set cover problem</span> Classical problem in combinatorics

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

In linear algebra, eigendecomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way. When the matrix being factorized is a normal or real symmetric matrix, the decomposition is called "spectral decomposition", derived from the spectral theorem.

Non-linear least squares is the form of least squares analysis used to fit a set of m observations with a model that is non-linear in n unknown parameters (m ≥ n). It is used in some forms of nonlinear regression. The basis of the method is to approximate the model by a linear one and to refine the parameters by successive iterations. There are many similarities to linear least squares, but also some significant differences. In economic theory, the non-linear least squares method is applied in (i) the probit regression, (ii) threshold regression, (iii) smooth regression, (iv) logistic link regression, (v) Box–Cox transformed regressors ( $).$

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets $S$ and $T$ , such that the number of edges between $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

In graph theory, the metric $k$ -center problem or vertex k-center problem is a classical combinatorial optimization problem studied in theoretical computer science that is NP-hard. Given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of $k$ vertices for which the largest distance of any point to its closest vertex in the $k$ -set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality. It has application in facility location and clustering.

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.

In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.

Parallel task scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule. In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter p_j and a size parameter q_j, and it must run for exactly p_j time-steps on exactly q_j machines in parallel.

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers, whose sum is k*T.

The configuration linear program (configuration-LP) is a linear programming technique used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem. Later, it has been applied to the bin packing and job scheduling problems. In the configuration-LP, there is a variable for each possible configuration - each possible multiset of items that can fit in a single bin. Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.

The Karmarkar–Karp (KK) bin packing algorithms are several related approximation algorithm for the bin packing problem. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is computationally hard. Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most $bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.$

References

↑ Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8.^: 112
↑ Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022). "The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches" (PDF). European Journal of Operational Research, 299 (2022), 945–959}.{{cite web}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
↑ Ajtai, Miklós (1973), "The solution of a problem of T. Radó", Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, 21: 61–63, MR 0319053
↑ Bereg, Sergey; Dumitrescu, Adrian; Jiang, Minghui (2010), "On covering problems of Rado", Algorithmica, 57 (3): 538–561, doi:10.1007/s00453-009-9298-z, MR 2609053 ; preliminary announcement in SWAT 2008, doi : 10.1007/978-3-540-69903-3_27
↑ Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "Selecting and covering colored points". Discrete Applied Mathematics. 250: 75–86. doi: 10.1016/j.dam.2018.05.011 . ISSN 0166-218X.
↑ Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (2020-08-01). "Approximation algorithms for geometric conflict free covering problems". Computational Geometry. 89: 101591. doi:10.1016/j.comgeo.2019.101591. ISSN 0925-7721. S2CID 209959954.
↑ Banik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (2020-01-01). "Parameterized Complexity of Geometric Covering Problems Having Conflicts". Algorithmica. 82 (1): 1–19. doi:10.1007/s00453-019-00600-w. ISSN 1432-0541. S2CID 254027914.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8.^: 112

[2] Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022). "The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches" (PDF). European Journal of Operational Research, 299 (2022), 945–959}.{{cite web}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)

[3] Ajtai, Miklós (1973), "The solution of a problem of T. Radó", Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques, 21: 61–63, MR 0319053

[4] Bereg, Sergey; Dumitrescu, Adrian; Jiang, Minghui (2010), "On covering problems of Rado", Algorithmica, 57 (3): 538–561, doi:10.1007/s00453-009-9298-z, MR 2609053 ; preliminary announcement in SWAT 2008, doi : 10.1007/978-3-540-69903-3_27

[5] Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "Selecting and covering colored points". Discrete Applied Mathematics. 250: 75–86. doi: 10.1016/j.dam.2018.05.011 . ISSN 0166-218X.

[6] Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (2020-08-01). "Approximation algorithms for geometric conflict free covering problems". Computational Geometry. 89: 101591. doi:10.1016/j.comgeo.2019.101591. ISSN 0925-7721. S2CID 209959954.

[7] Banik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (2020-01-01). "Parameterized Complexity of Geometric Covering Problems Having Conflicts". Algorithmica. 82 (1): 1–19. doi:10.1007/s00453-019-00600-w. ISSN 1432-0541. S2CID 254027914.

[1]

[2]

[5]

[6]

[7]