Imagen de Portada

Constraint Satisfaction Problems with Advice

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Ghoshal, Suprovat, Makarychev, Konstantin, Makarychev, Yury
Formato:	Preprint
Publicado:	2024
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)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
por: Makarychev, Yury
Publicado: (2026)

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

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

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)

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

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

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

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

Max Cut with Small-Dimensional SDP Solutions
por: Chang, Hsien-Chih, et al.
Publicado: (2026)

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

Online Computation with Untrusted Advice
por: Angelopoulos, Spyros, et al.
Publicado: (2019)

On the Advice Complexity of Online Matching on the Line
por: Csaba, Béla, et al.
Publicado: (2024)

Online Algorithms with Randomly Infused Advice
por: Emek, Yuval, et al.
Publicado: (2023)

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
por: Barto, Libor, et al.
Publicado: (2024)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
por: DeHaan, Ian, et al.
Publicado: (2025)

Warehouse Problem with Multiple Vendors and Generalized Complementarity Constraints
por: Bansal, Ishan, et al.
Publicado: (2024)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
por: Doron-Arad, Ilan, et al.
Publicado: (2023)

With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design
por: Canonne, Clément L., et al.
Publicado: (2025)

Removable Online Knapsack and Advice
por: Böckenhauer, Hans-Joachim, et al.
Publicado: (2020)

On Classifying Continuous Constraint Satisfaction Problems
por: Miltzow, Tillmann, et al.
Publicado: (2021)

On the Advice Complexity of Online Unit Clustering
por: Nagy-György, Judit
Publicado: (2023)

Improving Online Bin Covering with Little Advice
por: Brodnik, Andrej, et al.
Publicado: (2025)

Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
por: Jin, Billy, et al.
Publicado: (2022)

Subsequence Matching and LCS with Segment Number Constraints
por: Yonemoto, Yuki, et al.
Publicado: (2024)

Graph Exploration: The Impact of a Distance Constraint
por: Devismes, Stéphane, et al.
Publicado: (2024)

Improved Rank Aggregation under Fairness Constraint
por: Chakraborty, Diptarka, et al.
Publicado: (2025)

Dominating Set with Quotas: Balancing Coverage and Constraints
por: Chatterjee, Sobyasachi, et al.
Publicado: (2026)

Contract Scheduling with Distributional and Multiple Advice
por: Angelopoulos, Spyros, et al.
Publicado: (2024)

Subquadratic Submodular Maximization with a General Matroid Constraint
por: Kobayashi, Yusuke, et al.
Publicado: (2024)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
por: Inamdar, Tanmay, et al.
Publicado: (2024)

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

Space-Efficient Algorithm for Integer Programming with Few Constraints
por: Rohwedder, Lars, et al.
Publicado: (2024)

Bicriteria Algorithms for Submodular Cover with Partition and Fairness Constraints
por: Chen, Wenjing, et al.
Publicado: (2026)

Extending the Applicability of Bloom Filters by Relaxing their Parameter Constraints
por: Walther, Paul, et al.
Publicado: (2025)

LLM Query Scheduling with Prefix Reuse and Latency Constraints
por: Dexter, Gregory, et al.
Publicado: (2025)

Reconfiguring Multiple Connected Components with Size Multiset Constraints
por: Nakahata, Yu
Publicado: (2025)

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

Clustering under Constraints: Efficient Parameterized Approximation Schemes
por: Bhore, Sujoy, et al.
Publicado: (2025)