Weighted NP Optimization Problems: Logical Definability and Approximation Properties

DOI10.1137/S0097539795285102zbMATH Open0914.68074MaRDI QIDQ4210135

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

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Logical definability of NP optimization problems 👍 👎
• 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 👍 👎
• Parameterized Complexity of Weighted Satisfiability Problems 👍 👎
• SOFSEM 2005: Theory and Practice of Computer Science 👍 👎

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)