Sublinear-space approximation algorithms for Max r-SAT
From MaRDI portal
Sublinear-space approximation algorithms for Max \(r\)-SAT
Cites work
- \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
- A partial k-arboretum of graphs with bounded treewidth
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Approximating linear programming is log-space complete for P
- Approximation algorithms for combinatorial problems
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation in (poly-) logarithmic space
- Complexity of Partial Satisfaction
- Embedding and canonizing graphs of bounded genus in logspace
- Graph minors. III. Planar tree-width
- scientific article; zbMATH DE number 1256750 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Max NP-completeness made easy
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- New hash functions and their use in authentication and set equality
- On the Approximation of Maximum Satisfiability
- Relationships between nondeterministic and deterministic tape complexities
- Selection and sorting with limited storage
- Selection from read-only memory and sorting with minimum data movement
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Symmetric Complementation
- The complexity of planarity testing
- The design of approximation algorithms
- Tight bound on Johnson's algorithm for maximum satisfiability
- Undirected connectivity in log-space
- Upper bounds for time-space trade-offs in sorting and selection
This page was built for publication: Sublinear-space approximation algorithms for Max \(r\)-SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2695279)
