Cover Image

An Improved Algorithm for Sparse Instances of SAT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jain, Sanjay, Neoh, Tzeh Yuan, Stephan, Frank
Format:	Preprint
Published:	2024
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)

Online Allocation with Unknown Shared Supply
by: Neoh, Tzeh Yuan, et al.
Published: (2026)

New Algorithms for #2-SAT and #3-SAT
by: Peng, Junqiang, et al.
Published: (2025)

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

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

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
by: Gawrychowski, Paweł, et al.
Published: (2024)

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

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

A simple algorithm for Combinatorial n-fold ILPs using the Steinitz Lemma
by: Gupta, Sushmita, et al.
Published: (2025)

Efficient Algorithms to Compute Closed Substrings
by: Jain, Samkith K, et al.
Published: (2025)

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

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

Effective Traveling for Metric Instances of the Traveling Thief Problem
by: Eube, Jan, et al.
Published: (2026)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
by: Chekuri, Chandra, et al.
Published: (2024)

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

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

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
by: Chekuri, Chandra, et al.
Published: (2024)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
by: Gupta, Sushmita, et al.
Published: (2024)

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

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

Fast and Efficient Matching Algorithm with Deadline Instances
by: Song, Zhao, et al.
Published: (2023)

An Improved Pseudopolynomial Time Algorithm for Subset Sum
by: Chen, Lin, et al.
Published: (2024)

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

Improved Algorithms for Clustering with Noisy Distance Oracles
by: Pradhan, Pinki, et al.
Published: (2026)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

Improved Algorithms for Fair Matroid Submodular Maximization
by: Mahabadi, Sepideh, et al.
Published: (2026)

Improved Algorithms for Effective Resistance Computation on Graphs
by: Yang, Yichun, et al.
Published: (2025)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing
by: Lafond, Manuel
Published: (2024)

Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
by: Zhu, Yanhui, et al.
Published: (2024)

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

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
by: Armbruster, Alexander, et al.
Published: (2026)

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

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
by: Ferber, Asaf, et al.
Published: (2025)