Imagen de Portada

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Makarychev, Yury
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
por: Ghoshal, Suprovat, et al.
Publicado: (2026)

Hardness of Approximation for Shortest Path with Vector Costs
por: Carlson, Charlie, et al.
Publicado: (2025)

Constraint Satisfaction Problems with Advice
por: Ghoshal, Suprovat, et al.
Publicado: (2024)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
por: Makarychev, Yury, et al.
Publicado: (2024)

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

Parameterised algorithms for temporally satisfying reconfiguration problems
por: Davot, Tom, et al.
Publicado: (2025)

Sampling permutations satisfying constraints within the lopsided local lemma regime
por: He, Kun, et al.
Publicado: (2024)

Max-Cut with Multiple Cardinality Constraints
por: Makarychev, Yury, et al.
Publicado: (2025)

The PRODSAT phase of random quantum satisfiability
por: Lee, Joon, et al.
Publicado: (2024)

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

Designing sparse temporal graphs satisfying connectivity requirements
por: Bellitto, Thomas, et al.
Publicado: (2026)

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

Linear Space Streaming Lower Bounds for Approximating CSPs
por: Chou, Chi-Ning, et al.
Publicado: (2021)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
por: Singer, Noah G.
Publicado: (2025)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
por: Dalirrooyfard, Mina, et al.
Publicado: (2026)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
por: Dalirrooyfard, Mina, et al.
Publicado: (2025)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
por: Dalirrooyfard, Mina, et al.
Publicado: (2024)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
por: Singer, Noah G., et al.
Publicado: (2026)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
por: Anand, Aditya, et al.
Publicado: (2025)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
por: Bandyapadhyay, Sayan, et al.
Publicado: (2024)

Additive Sparsification of CSPs
por: Pelleg, Eden, et al.
Publicado: (2021)

Single-Pass Streaming CSPs via Two-Tier Sampling
por: Azarmehr, Amir, et al.
Publicado: (2026)

Optimal Phylogenetic Reconstruction from Sampled Quartets
por: Arvanitakis, Dionysis, et al.
Publicado: (2026)

List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I
por: Jeronimo, Fernando Granha, et al.
Publicado: (2025)

Solving Random Planted CSPs below the $n^{k/2}$ Threshold
por: Basu, Arpon, et al.
Publicado: (2025)

A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
por: Elkin, Yury, et al.
Publicado: (2021)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
por: Makarychev, Konstantin, et al.
Publicado: (2025)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
por: Sharma, Amatya, et al.
Publicado: (2026)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
por: Sharma, Amatya, et al.
Publicado: (2026)

Near-Optimal Space Lower Bounds for Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2025)

Sketching approximations and LP approximations for finite CSPs are related
por: Singer, Noah G., et al.
Publicado: (2025)

Tight Bounds for Sparsifying Random CSPs
por: Brakensiek, Joshua, et al.
Publicado: (2025)

Approximation and parameterized algorithms for covering disjointness-compliable set families
por: Nutov, Zeev, et al.
Publicado: (2025)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
por: Fei, Yumou
Publicado: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
por: Jansen, Bart M. P., et al.
Publicado: (2026)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
por: Jonsson, Peter, et al.
Publicado: (2025)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
por: Kim, Eun Jung, et al.
Publicado: (2022)

MNL-Bandit with Knapsacks: a near-optimal algorithm
por: Aznag, Abdellah, et al.
Publicado: (2021)

A nearly optimal randomized algorithm for explorable heap selection
por: Borst, Sander, et al.
Publicado: (2022)