An inequality for polymatroid functions and its applications.
From MaRDI portal
Publication:1410680
DOI10.1016/S0166-218X(02)00455-9zbMath1033.05023OpenAlexW1977557143WikidataQ59560608 ScholiaQ59560608MaRDI QIDQ1410680
Endre Boros, Leonid G. Khachiyan, Vladimir A. Gurvich, Khaled M. Elbassioni
Publication date: 14 October 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00455-9
Hypergraphs (05C65) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
Improved bounds for the greedy strategy in optimization problems with curvature ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Performance bounds with curvature for batched greedy optimization
Cites Work
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- Random generation of combinatorial structures from a uniform distribution
- Dualization of regular Boolean functions
- An O(m n) algorithm for regular set-covering problems
- On generating all maximal independent sets
- NP-completeness of some generalizations of the maximum matching problem
- On the approximability of the maximum induced matching problem
- Interior and exterior functions of Boolean functions
- Minimum self-dual decompositions of positive dual-minor Boolean functions
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Complexity of identification and dualization of positive Boolean functions
- Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
- On graphs with polynomially solvable maximum-weight clique problem
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- Rado's theorem for polymatroids
- A New Algorithm for Generating All the Maximal Independent Sets
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An inequality for polymatroid functions and its applications.
