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

DOI10.1016/S0304-3975(00)00016-5MaRDI QIDQ5941283zbMATH OpenOpenAlexFDO

Authors Dawei Hong, J.-C. Birget

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)

Recommendations

• scientific article; zbMATH DE number 847149
• scientific article; zbMATH DE number 3999286
• Probabilistic behaviour of optimal bin-packing solutions
• On a dual version of the one-dimensional bin packing problem
• scientific article; zbMATH DE number 168445

Cites work

• Approximation algorithms for combinatorial problems
• Completeness in approximation classes
• Empirical processes
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3751899 (Why is no real title available?)
• scientific article; zbMATH DE number 52589 (Why is no real title available?)
• Probabilistic analysis of a bin covering algorithm
• Probability Inequalities for Sums of Bounded Random Variables
• Weighted sums of certain dependent random variables

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941283)