Imagen de Portada

Complexity of Local Search for CSPs Parameterized by Constraint Difference

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Anand, Aditya, Cohen-Addad, Vincent, d'Orsi, Tommaso, Gupta, Anupam, Lee, Euiwoong, Panigrahi, Debmalya, Peng, Sijin
Formato:	Preprint
Publicado:	2025
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

Max-Cut with $ε$-Accurate Predictions
por: Cohen-Addad, Vincent, et al.
Publicado: (2024)

Combinatorial Optimization using Comparison Oracles
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
por: Cohen-Addad, Vincent, et al.
Publicado: (2024)

Multi-View Stochastic Block Models
por: Cohen-Addad, Vincent, et al.
Publicado: (2024)

On Purely Private Covariance Estimation
por: d'Orsi, Tommaso, et al.
Publicado: (2025)

Tight Differentially Private PCA via Matrix Coherence
por: d'Orsi, Tommaso, et al.
Publicado: (2025)

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

Perturb-and-Project: Differentially Private Similarities and Marginals
por: Cohen-Addad, Vincent, et al.
Publicado: (2024)

Min-CSPs on Complete Instances
por: Anand, Aditya, et al.
Publicado: (2024)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
por: Cohen-Addad, Vincent, et al.
Publicado: (2022)

Separating $k$-Median from the Supplier Version
por: Anand, Aditya, et al.
Publicado: (2024)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

Understanding the Cluster LP for Correlation Clustering
por: Cao, Nairen, et al.
Publicado: (2024)

An Improved Greedy Approximation for (Metric) $k$-Means
por: Charikar, Moses, et al.
Publicado: (2026)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
por: d'Orsi, Tommaso, et al.
Publicado: (2024)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
por: Anand, Aditya, et al.
Publicado: (2025)

Approximating Small Sparse Cuts
por: Anand, Aditya, et al.
Publicado: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
por: Cohen-Addad, Vincent, et al.
Publicado: (2026)

Nearly Tight Bounds for the Online Sorting Problem
por: Azar, Yossi, et al.
Publicado: (2025)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

Unbreakable Decomposition in Close-to-Linear Time
por: Anand, Aditya, et al.
Publicado: (2024)

Hypergraph Unreliability in Quasi-Polynomial Time
por: Cen, Ruoxu, et al.
Publicado: (2024)

Network Unreliability in Almost-Linear Time
por: Cen, Ruoxu, et al.
Publicado: (2025)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
por: Bhattacharya, Sayan, et al.
Publicado: (2025)

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

Private graphon estimation via sum-of-squares
por: Chen, Hongjie, et al.
Publicado: (2024)

Matroid-Based TSP Rounding for Half-Integral Solutions
por: Gupta, Anupam, et al.
Publicado: (2021)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
por: Cohen-Addad, Vincent, et al.
Publicado: (2026)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
por: S., Karthik C., et al.
Publicado: (2024)

Solving the Correlation Cluster LP in Sublinear Time
por: Cao, Nairen, et al.
Publicado: (2025)

Static to Dynamic Correlation Clustering
por: Cao, Nairen, et al.
Publicado: (2025)

Distributed Algorithms for Euclidean Clustering
por: Cohen-Addad, Vincent, et al.
Publicado: (2026)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

Language Generation in the Limit: Noise, Loss, and Feedback
por: Bai, Yannan, et al.
Publicado: (2025)

Correlation Clustering Beyond the Pivot Algorithm
por: Behnezhad, Soheil, et al.
Publicado: (2024)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
por: Bansal, Nikhil, et al.
Publicado: (2024)

Dynamic Correlation Clustering in Sublinear Update Time
por: Cohen-Addad, Vincent, et al.
Publicado: (2024)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
por: Beretta, Lorenzo, et al.
Publicado: (2025)

Retriever Portfolios: A Principled Approach to Adaptive RAG
por: Stouras, Miltiadis, et al.
Publicado: (2026)