Polynomial-time algorithms for regular set-covering and threshold synthesis
type: Item
instance of: scholarly article
title: Polynomial-time algorithms for regular set-covering and threshold synthesis
zbMATH Open document ID: 0619.05020
DOI: 10.1016/0166-218X(85)90040-X
author: Bruno Simeone
author: Uri N. Peled
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: A set-covering problem is called regular if a cover always remains a cover when any column in it is replaced by an earlier column. From the input of the problem - the coefficient matrix of the set-covering inequalities - it is possible to check in polynomial time whether the problem is regular or can be made regular by permuting the columns. If it is, then all the minimal covers are generated in polynomial time, and one of them is an optimal solution. The algorithm also yields an explicit bound for the number of minimal covers. These results can be used to check in polynomial time whether a given set-covering problem is equivalent to some knapsack problem without additional variables, or equivalently to recognize positive threshold functions in polynomial time. However, the problem of recognizing when an arbitrary Boolean function is threshold is NP-complete. It is also shown that the list of maximal non-covers is essentially the most compact input possible, even if it is known in advance that the problem is regular.
Mathematics Subject Classification ID: 05B40
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 4004205
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: NP-completeness
zbMATH Keywords: set-covering problem
zbMATH Keywords: knapsack problem
zbMATH Keywords: threshold functions
MaRDI profile type: Publication
cites work: Coefficient reduction for inequalities in 0–1 variables
cites work: Q4165164
cites work: Bottleneck extrema
cites work: Regular (2, 2)-systems
cites work: A characterization of threshold matroids
cites work: An Algorithm to Dualize a Regular Switching Function
cites work: A new polynomial-time algorithm for linear programming
cites work: On Dedekind's Problem: The Number of Isotone Boolean Functions. II
cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
cites work: Q3929672
cites work: On the unimodality of some partition polynomials
cites work: Solution of Two Difficult Combinatorial Problems with Linear Algebra
cites work: Q5822054
cites work: Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
cites work: Q5607242
cites work: Faces for a linear inequality in 0–1 variables
full work available at URL: 0166-218x(85)90040-x
OpenAlex ID: W1969423858
Recommended article: An O(m n) algorithm for regular set-covering problems
Recommended article: A Class of Polynomially Solvable Set-Covering Problems
Recommended article: Algorithms and Computation
Recommended article: A Pretty Complete Combinatorial Algorithm for the Threshold Synthesis Problem
Recommended article: Complexity and approximability of the cover polynomial
Recommended article: Exact Algorithms for Set Multicover and Multiset Multicover Problems
Recommended article: The set covering problem: Complexity, algorithms, experiments
Recommended article: Algorithms for the set covering problem
Recommended article: A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
Recommended article: Sublinear circuits for polyhedral sets
description: scientific article; zbMATH DE number 4004205