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

surveyrandom pseudo-polynomial algorithmsweighted combinatorial problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Random pseudo-polynomial algorithms for some combinatorial programming problems