Cover Image

New Algorithms for #2-SAT and #3-SAT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Peng, Junqiang, Sheng, Zimo, Xiao, Mingyu
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
by: Jain, Sanjay, et al.
Published: (2026)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
by: Zhao, Jingyang, et al.
Published: (2025)

A Polynomial time Algorithm for 3SAT
by: Du, Lizhi
Published: (2010)

An Improved Algorithm for Sparse Instances of SAT
by: Jain, Sanjay, et al.
Published: (2024)

A Polynomial Decision for 3-SAT
by: Weiss, Angela
Published: (2022)

Maximum And- vs. Even-SAT
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Algorithms Transcending the SAT-Symmetry Interface
by: Anders, Markus, et al.
Published: (2023)

Computing diverse pair of solutions for tractable SAT
by: Gima, Tatsuya, et al.
Published: (2024)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
by: Austrin, Per, et al.
Published: (2024)

On the Mysteries of MAX NAE-SAT
by: Brakensiek, Joshua, et al.
Published: (2020)

On the Parameterized Complexity of Diverse SAT
by: Misra, Neeldhara, et al.
Published: (2024)

Geometric Interpretation of 3-SAT and Phase Transition
by: Gillet, Frederic
Published: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

Quantum Graph-State Synthesis with SAT
by: Brand, Sebastiaan, et al.
Published: (2023)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)

Further Explanations on "SAT Requires Exhaustive Search"
by: Dong, Qingxiu, et al.
Published: (2024)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

Counting random $k$-SAT near the satisfiability threshold
by: Chen, Zongchen, et al.
Published: (2024)

Random local access for sampling k-SAT solutions
by: Dong, Dingding, et al.
Published: (2024)

satsuma: Structure-based Symmetry Breaking in SAT
by: Anders, Markus, et al.
Published: (2024)

An Improved Approximation Algorithm for Metric Triangle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Assessing fault-tolerant quantum advantage for $k$-SAT with structure
by: Brehm, Martijn, et al.
Published: (2024)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
by: Liu, Yuxi, et al.
Published: (2023)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
by: Zhao, Jingyang, et al.
Published: (2023)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
by: Zhao, Jingyang, et al.
Published: (2022)

A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
by: Xiong, Ziliang, et al.
Published: (2024)

One-Shot Learning for k-SAT
by: Galanis, Andreas, et al.
Published: (2025)

An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling
by: Zhao, Jingyang, et al.
Published: (2025)

A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
by: Tian, Kangyi, et al.
Published: (2026)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
by: Manurangsi, Pasin
Published: (2024)

How Hard Is It to Rig a Tournament When Few Players Can Beat or Be Beaten by the Favorite?
by: Wang, Zhonghao, et al.
Published: (2026)

Microscopic Structure of Random 3-SAT: A Discrete Geometric Approach to Phase Transitions and Algorithmic Complexity
by: Zhan, Yongjian
Published: (2026)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2025)

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
by: Liu, Yuxi, et al.
Published: (2026)