On systems of linear equations with two variables per equation

DOI10.1007/978-3-540-27821-4_11MaRDI QIDQ5313015zbMATH OpenOpenAlexFDO

Authors Daniel Reichman, Uriel Feige

Publication date 25 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99805

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Improved NP-inapproximability for 2-variable linear equations
• scientific article; zbMATH DE number 6823767
• Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups
• NP-hardness of approximately solving linear equations over reals
• On the hardness of approximating max-satisfy

Cited in

(11)

• Minimal achievable approximation ratio for MAX-MQ in finite fields
• On the hardness of approximating max-satisfy
• Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups
• \(\mathcal{NP}\)-hardness of approximately solving linear equations over reals
• Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
• Improved NP-inapproximability for 2-variable linear equations
• On the hardness of approximating balanced homogenous 3-Lin
• NP-hardness of approximately solving linear equations over reals
• scientific article; zbMATH DE number 7650072 (Why is no real title available?)
• A note on unique games
• Approximating maximum satisfiable subsystems of linear equations of bounded width

This page was built for publication: On systems of linear equations with two variables per equation

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