Covering problems

Last updated June 16, 2024

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]

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:^[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).

Conflict-free covering

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

In mathematics, a set $B$ of vectors in a vector space $V$ is called a basis if every element of $V$ may be written in a unique way as a finite linear combination of elements of $B$ . The coefficients of this linear combination are referred to as components or coordinates of the vector with respect to $B$ . The elements of a basis are called basis vectors.

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 and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

In machine learning, support vector machines are supervised max-margin models with associated learning algorithms that analyze data for classification and regression analysis. Developed at AT&T Bell Laboratories by Vladimir Vapnik with colleagues SVMs are one of the most studied models, being based on statistical learning frameworks of VC theory proposed by Vapnik and Chervonenkis (1974).

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

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

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 in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value which is at least $times the correct value, and at most times the correct value.$

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.

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) CS1 maint: numeric 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) CS1 maint: numeric 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]