Average-case non-approximability of optimisation problems

DOI10.1007/S00224-007-2012-0zbMATH Open1176.90671OpenAlexW2077543835MaRDI QIDQ2642911

Birgit Schelm

Publication date: 6 September 2007

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-2012-0

zbMATH Keywords

hierarchy results\(p\)-computable input distributions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Average case optimality for linear problems

This page was built for publication: Average-case non-approximability of optimisation problems

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