Polynomial-time algorithms for regular set-covering and threshold synthesis
From MaRDI portal
Publication:1089348
DOI10.1016/0166-218X(85)90040-XzbMATH Open0619.05020OpenAlexW1969423858MaRDI QIDQ1089348FDOQ1089348
Authors: Bruno Simeone, Uri N. Peled 
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(85)90040-x
Recommendations
- An O(m n) algorithm for regular set-covering problems
- A Class of Polynomially Solvable Set-Covering Problems
- Algorithms and Computation
- A pretty complete combinatorial algorithm for the threshold synthesis problem
- Complexity and approximability of the cover polynomial
- Exact algorithms for set multicover and multiset multicover problems
- The set covering problem: Complexity, algorithms, experiments
- Algorithms for the set covering problem
- A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
- Sublinear circuits for polyhedral sets
Cites Work
- A new polynomial-time algorithm for linear programming
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
- Faces for a linear inequality in 0–1 variables
- Title not available (Why is that?)
- On Dedekind's Problem: The Number of Isotone Boolean Functions. II
- Bottleneck extrema
- On the unimodality of some partition polynomials
- Solution of Two Difficult Combinatorial Problems with Linear Algebra
- Title not available (Why is that?)
- A characterization of threshold matroids
- Regular (2, 2)-systems
- An Algorithm to Dualize a Regular Switching Function
- Title not available (Why is that?)
- Coefficient reduction for inequalities in 0–1 variables
- Title not available (Why is that?)
Cited In (32)
- Counting and enumerating aggregate classifiers
- Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
- Simple games versus weighted voting games: bounding the critical threshold value
- Monotone clutters
- On the complexity of problems on simple games
- Linear separation of connected dominating sets in graphs
- Dual-bounded generating problems: Weighted transversals of a hypergraph
- The threshold order of a Boolean function
- Sets uniquely determined by projections on axes. II: Discrete case
- Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
- Tree-shellability of Boolean functions
- On the characterization of weighted simple games
- Boolean minors
- A special case of set covering problems
- Decompositions of positive self-dual Boolean functions
- Trading transforms of non-weighted simple games and integer weights of weighted simple games
- Minimum self-dual decompositions of positive dual-minor Boolean functions
- On the complexity of the decisive problem in simple and weighted games
- Decomposing 1-Sperner hypergraphs
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
- Joint realizability of monotone Boolean functions
- On minimum sum representations for weighted voting games
- Generating dual-bounded hypergraphs
- Computational aspects of monotone dualization: a brief survey
- Enumeration of weighted games with minimum and an analysis of voting power for bipartite complete games with minimum
- On the geometric separability of Boolean functions
- Dualization of regular Boolean functions
- A note on the growth of the dimension in complete simple games
- An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
- Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
- Forms of representation for simple games: sizes, conversions and equivalences
- An O(m n) algorithm for regular set-covering problems
This page was built for publication: Polynomial-time algorithms for regular set-covering and threshold synthesis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089348)
