Polynomial approximation: a structural and operational study. (Abstract of thesis)

DOI10.1007/s10288-006-0027-zzbMath1218.90170OpenAlexW2017469925MaRDI QIDQ2644383

Bruno Escoffier

Publication date: 31 August 2007

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-006-0027-z

zbMATH Keywords

combinatorial optimizationapproximationcompletenessdifferential ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• A coloring problem for weighted graphs
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Approximate solution of NP optimization problems
• Differential approximation of MIN SAT, MAX SAT and related problems
• Weighted coloring: further complexity and approximability results
• Optimization, approximation, and complexity classes
• Logical definability of NP optimization problems
• Probabilistic Combinatorial Optimization on Graphs
• Proving completeness by logic
• Algorithms and Computation

This page was built for publication: Polynomial approximation: a structural and operational study. (Abstract of thesis)