Random pseudo-polynomial algorithms for some combinatorial programming problems

DOI10.1016/0377-2217(92)90209-RzbMath0757.90066MaRDI QIDQ1194734

Giulia Galbiati, Francesco Maffioli

Publication date: 6 October 1992

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

survey; random pseudo-polynomial algorithms; weighted combinatorial problems

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C10: Integer programming

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized algorithms in combinatorial optimization: A survey
• Matching theory
• Exact arborescences, matchings and cycles
• Matching is as easy as matrix inversion
• The image of weighted combinatorial problems
• On the computation of pfaffians
• Intersection of Two Matroids: (Condensed) Border Graphs and Ranking
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Random pseudo-polynomial algorithms for exact matroid problems
• Systems of distinct representatives and linear algebra