Weighted NP Optimization Problems: Logical Definability and Approximation Properties

DOI10.1137/S0097539795285102MaRDI QIDQ4210135zbMATH OpenFDO

Authors Marius Zimand

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

approximation propertiesNP optimization problemslogical definabilitymultiprover interactive systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Logical definability of NP optimization problems
• Parameterized complexity of weighted satisfiability problems
• scientific article; zbMATH DE number 847149
• scientific article; zbMATH DE number 1944142
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• On variable-weighted exact satisfiability problems
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• SOFSEM 2005: Theory and Practice of Computer Science
• Publication:3484326
• scientific article; zbMATH DE number 515741

Cited in

(4)

• scientific article; zbMATH DE number 515741 (Why is no real title available?)
• Logical definability of NP optimization problems
• Approximation properties of NP minimization classes
• On weighted vs unweighted versions of combinatorial optimization problems

This page was built for publication: Weighted NP Optimization Problems: Logical Definability and Approximation Properties

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