Covering problems

Last updated September 05, 2023

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 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]

For Petri nets, for example, 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 and conflict-free 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:^[3]

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

A more general notion is conflict-free covering.^[4] 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^[5] 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

$<span class="mw-page-title-main">Hausdorff dimension</span> Invariant measure of fractal dimension$

In mathematics, Hausdorff dimension is a measure of roughness, or more specifically, fractal dimension, that was introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of a line segment is 1, of a square is 2, and of a cube is 3. That is, for sets of points that define a smooth shape or a shape that has a small number of corners—the shapes of traditional geometry and science—the Hausdorff dimension is an integer agreeing with the usual sense of dimension, also known as the topological dimension. However, formulas have also been developed that allow calculation of the dimension of other less simple objects, where, solely on the basis of their properties of scaling and self-similarity, one is led to the conclusion that particular objects—including fractals—have non-integer Hausdorff dimensions. Because of the significant technical advances made by Abram Samoilovitch Besicovitch allowing computation of dimensions for highly irregular or "rough" sets, this dimension is also commonly referred to as the Hausdorff–Besicovitch dimension.

Linear algebra is the branch of mathematics concerning linear equations such as:

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

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

The Frank–Wolfe algorithm is an iterative first-order optimization algorithm for constrained convex optimization. Also known as the conditional gradient method, reduced gradient algorithm and the convex combination algorithm, the method was originally proposed by Marguerite Frank and Philip Wolfe in 1956. In each iteration, the Frank–Wolfe algorithm considers a linear approximation of the objective function, and moves towards a minimizer of this linear function.

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 ( $).$

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.

The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space $where is a universe of points in and is a family of subsets of called ranges, defined by the intersection of and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset of ranges such that every point in the universe is covered by some range in .$

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)
↑ 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)

[3] 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.

[4] 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.

[5] 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]

[3]

[4]

[5]