Approximation of some NP-hard optimization problems by finite machines, in probability

DOI10.1016/S0304-3975(00)00016-5zbMath0973.68084OpenAlexW1989694826MaRDI QIDQ5941283

Jean-Camille Birget, Dawei Hong

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00016-5

zbMATH Keywords

approximationfinite-state machinesNP-optimization problemsprobabilistic analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness in approximation classes
• Approximation algorithms for combinatorial problems
• Probabilistic analysis of a bin covering algorithm
• Weighted sums of certain dependent random variables
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: Approximation of some NP-hard optimization problems by finite machines, in probability