Cover Image

Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dabrowski, Konrad K., Jonsson, Peter, Ordyniak, Sebastian, Osipov, George, Wahlström, Magnus
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms F.2.2; G.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parameterized Complexity of MinCSP over the Point Algebra
by: Osipov, George, et al.
Published: (2023)

Parameterized Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2025)

Optimal FPT-Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2026)

Algorithms and Complexity of Difference Logic
by: Dabrowski, Konrad K., et al.
Published: (2024)

Backdoors for Quantified Boolean Formulas
by: Eriksson, Leif, et al.
Published: (2026)

Faster algorithms on linear delta-matroids
by: Koana, Tomohiro, et al.
Published: (2024)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
by: Bougeret, Marin, et al.
Published: (2024)

A Tight Subexponential-time Algorithm for Two-Page Book Embedding
by: Ganian, Robert, et al.
Published: (2024)

Partial Implementation of Max Flow and Min Cost Flow in Almost-Linear Time
by: Kavi, Nithin
Published: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

Structural Parameterization of Steiner Tree Packing
by: Hastrich, Niko, et al.
Published: (2025)

Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width
by: Bergougnoux, Benjamin, et al.
Published: (2026)

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

Set Parameterized Matching via Multi-Layer Hashing
by: Lewenstein, Moshe, et al.
Published: (2026)

On the Parameterized Complexity of Diverse SAT
by: Misra, Neeldhara, et al.
Published: (2024)

Approximating Multiplicatively Weighted Voronoi Diagrams: Efficient Construction with Linear Size
by: Gudmundsson, Joachim, et al.
Published: (2021)

A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs
by: Bringolf, Jeffrey, et al.
Published: (2025)

On Hardness and Approximation of Broadcasting in Structured Graphs
by: Bringolf, Jeffrey, et al.
Published: (2025)

Approximately Partitioning Vertices into Short Paths
by: Gong, Mingyang, et al.
Published: (2026)

Approximation algorithms for scheduling with rejection in green manufacturing
by: Gong, Mingyang, et al.
Published: (2025)

Approximation algorithms for Job Scheduling with reconfigurable resources
by: Bergé, Pierre, et al.
Published: (2023)

On the Approximability of Unsplittable Flow on a Path with Time Windows
by: Armbruster, Alexander, et al.
Published: (2025)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
by: Krithika, R., et al.
Published: (2023)

Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity
by: Dreier, Jan, et al.
Published: (2026)

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

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
by: Mosenzon, Ron
Published: (2025)

Approximating the Average-Case Graph Search Problem with Non-Uniform Costs
by: Szyfelbein, Michał
Published: (2025)

Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
by: Randolph, Tim, et al.
Published: (2024)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
by: Boneh, Itai, et al.
Published: (2025)

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
by: Ahn, Jungho, et al.
Published: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
by: DeHaan, Ian, et al.
Published: (2024)

Connected Components in Linear Work and Near-Optimal Time
by: Farhadi, Alireza, et al.
Published: (2023)

Approximation Algorithms for Action-Reward Query-Commit Matching
by: Derakhshan, Mahsa, et al.
Published: (2026)

On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2026)

Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees
by: Høgemo, Svein
Published: (2024)

Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio
by: Kanellopoulos, Sotiris, et al.
Published: (2025)

Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
by: Eiben, Eduard, et al.
Published: (2023)

Exploiting Low Scanwidth to Resolve Soft Polytomies
by: Bruchhold, Sebastian, et al.
Published: (2025)

Online $b$-Matching with Stochastic Rewards
by: Albers, Susanne, et al.
Published: (2024)