Sublinear-space approximation algorithms for Max \(r\)-SAT
From MaRDI portal
Publication:2695279
DOI10.1007/978-3-030-89543-3_11OpenAlexW3209831490MaRDI QIDQ2695279
Venkatesh Raman, Arindam Biswas
Publication date: 30 March 2023
Full work available at URL: https://arxiv.org/abs/2107.01673
Cites Work
- Unnamed Item
- Unnamed Item
- Selection from read-only memory and sorting with minimum data movement
- Approximating linear programming is log-space complete for P
- Graph minors. III. Planar tree-width
- Upper bounds for time-space trade-offs in sorting and selection
- Selection and sorting with limited storage
- New hash functions and their use in authentication and set equality
- Approximation algorithms for combinatorial problems
- A partial k-arboretum of graphs with bounded treewidth
- Tight bound on Johnson's algorithm for maximum satisfiability
- The complexity of planarity testing
- Max NP-completeness made easy
- Approximation in (Poly-) logarithmic space
- Relationships between nondeterministic and deterministic tape complexities
- $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
- The Design of Approximation Algorithms
- Undirected connectivity in log-space
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Symmetric Complementation
- Complexity of Partial Satisfaction
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Approximation algorithms for NP-complete problems on planar graphs
- On the Approximation of Maximum Satisfiability
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Embedding and canonizing graphs of bounded genus in logspace
This page was built for publication: Sublinear-space approximation algorithms for Max \(r\)-SAT
