Buchumschlag

Additive Sparsification of CSPs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Pelleg, Eden, Živný, Stanislav
Format:	Preprint
Veröffentlicht:	2021
Schlagworte:	Data Structures and Algorithms Discrete Mathematics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An approximation algorithm for Maximum DiCut vs. Cut
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
von: Bedert, Benjamin, et al.
Veröffentlicht: (2025)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
von: Shao, Shuai, et al.
Veröffentlicht: (2023)

The periodic structure of local consistency
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2024)

Maximum $k$- vs. $\ell$-colourings of graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2023)

On the complexity of symmetric vs. functional PCSPs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2022)

A Dichotomy for Maximum PCSPs on Graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

A logarithmic approximation of linearly ordered colourings
von: Håstad, Johan, et al.
Veröffentlicht: (2024)

Semidefinite programming and linear equations vs. homomorphism problems
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

Tight Bounds for Sparsifying Random CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

Palette Sparsification for Graphs with Sparse Neighborhoods
von: Dhawan, Abhishek
Veröffentlicht: (2024)

A note on approximating the average degree of bounded arboricity graphs
von: Eden, Talya, et al.
Veröffentlicht: (2026)

Constructive l2-Discrepancy Minimization with Additive Deviations
von: Dutta, Kunal
Veröffentlicht: (2025)

Pliability and Approximating Max-CSPs
von: Romero, Miguel, et al.
Veröffentlicht: (2019)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
von: Avila, Tatiana Rocha, et al.
Veröffentlicht: (2026)

A polynomial kernel for vertex deletion into bipartite permutation graphs
von: Derbisz, Jan
Veröffentlicht: (2021)

Fairness in Repetitive Scheduling
von: Hermelin, Danny, et al.
Veröffentlicht: (2021)

Hop-Constrained Metric Embeddings and their Applications
von: Filtser, Arnold
Veröffentlicht: (2021)

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
von: Brubach, Brian, et al.
Veröffentlicht: (2021)

String Matching with a Dynamic Pattern
von: Monteiro, Bruno, et al.
Veröffentlicht: (2025)

Tight Localizations of Feedback Sets
von: Hecht, Michael, et al.
Veröffentlicht: (2020)

Inverse matroid optimization under subset constraints
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
von: Jordon, Addie, et al.
Veröffentlicht: (2025)

Graph Coloring Below Guarantees via Co-Triangle Packing
von: Akmal, Shyan, et al.
Veröffentlicht: (2025)

Fast Makespan Minimization via Short ILPs
von: Hermelin, Danny, et al.
Veröffentlicht: (2026)

An Approximation Algorithm for Monotone Submodular Cost Allocation
von: Mizutani, Ryuhei
Veröffentlicht: (2025)

Greedy Algorithms for Shortcut Sets and Hopsets
von: Bals, Ben, et al.
Veröffentlicht: (2025)

A Unified Approach to Minimizing Symmetric Submodular Functions
von: Iwata, Satoru, et al.
Veröffentlicht: (2026)

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
von: Tan, Jingjing
Veröffentlicht: (2024)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
von: Harada, Tsubasa
Veröffentlicht: (2024)

Max Weight Independent Set in sparse graphs with no long claws
von: Abrishami, Tara, et al.
Veröffentlicht: (2023)

Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac
von: Ingels, Florian
Veröffentlicht: (2023)

Online Graph Balancing and the Power of Two Choices
von: Bansal, Nikhil, et al.
Veröffentlicht: (2026)

Exponential Time Approximation for Coloring 3-Colorable Graphs
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Solving the List Coloring Problem through a Branch-and-Price algorithm
von: Lucci, Mauro, et al.
Veröffentlicht: (2023)

Approximating Submodular Matroid-Constrained Partitioning
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Continuous optimization methods for the graph isomorphism problem
von: Klus, Stefan, et al.
Veröffentlicht: (2023)

Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
von: Alaoui, Ziad Ismaili, et al.
Veröffentlicht: (2025)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
von: Veldt, Nate
Veröffentlicht: (2025)