scientific article; zbMATH DE number 2077131

zbMATH Open1044.68942MaRDI QIDQ4470516FDOQ4470516

Authors Pilu Crescenzi, Luca Trevisan

Publication date 1 July 2004

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cited in

(10)

• Local search, reducibility and approximability of NP-optimization problems
• Structural properties of bounded relations with an application to NP optimization problems
• Max NP-completeness made easy
• On weighted vs unweighted versions of combinatorial optimization problems
• Genetic local search and hardness of approximation for the server load balancing problem
• The simplified partial digest problem: approximation and a graph-theoretic model
• Structure in approximation classes
• Bounded queries, approximations, and the Boolean hierarchy
• Approximate solution of NP optimization problems
• Improved non-approximability results for minimum vertex cover with density constraints

This page was built for publication:

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