Revisiting maximum satisfiability and related problems in data streams
From MaRDI portal
Publication:6199395
DOI10.1016/j.tcs.2023.114271OpenAlexW4388010188MaRDI QIDQ6199395
Publication date: 23 February 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114271
Cites Work
- Unnamed Item
- Unnamed Item
- Some simplified NP-complete graph problems
- On randomized one-round communication complexity
- On dependent randomized rounding algorithms
- On approximation algorithms for the minimum satisfiability problem
- Parallel approximation algorithms by positive linear programming
- A constraint optimization approach to causal discovery from subsampled time series data
- Maximum satisfiability in software analysis: applications and techniques
- Random sampling with a reservoir
- The Minimum Satisfiability Problem
- On the Approximation of Maximum Satisfiability
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- An optimal space lower bound for approximating MAX-CUT
- Sublinear Algorithms for (Δ + 1) Vertex Coloring
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Some optimal inapproximability results
- The complexity of theorem-proving procedures
- Approximation and Online Algorithms
