Cover Image

Clustering with Locally Bounded Ignorance

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Garvardt, Jaroslav, Komusiewicz, Christian
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Complexity Analysis of the c-Closed Vertex Deletion Problem
by: Lehner, Lisa, et al.
Published: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Kernelization Bounds for Constrained Coloring
by: Haviv, Ishay
Published: (2026)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

The Structure of In-Place Space-Bounded Computation
by: Cook, James, et al.
Published: (2025)

Residue Domination in Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2024)

Improved Space Bounds for Subset Sum
by: Belova, Tatiana, et al.
Published: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Cluster Editing on Cographs and Related Classes
by: Lafond, Manuel, et al.
Published: (2024)

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

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

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

On the complexity and approximability of Bounded access Lempel Ziv coding
by: Cicalese, Ferdinando, et al.
Published: (2024)

Structural Parameterizations for Two Bounded Degree Problems Revisited
by: Lampis, Michael, et al.
Published: (2023)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Locality Bounds for Sampling Hamming Slices
by: Kane, Daniel M., et al.
Published: (2024)

Bandwidth Parameterized by Cluster Vertex Deletion Number
by: Gima, Tatsuya, et al.
Published: (2023)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

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

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
by: Abu-Khzam, Faisal N., et al.
Published: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
by: Ko, Young Kun
Published: (2025)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
by: Wang, Chengu
Published: (2026)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
by: Kothari, Pravesh K., et al.
Published: (2025)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
by: Hu, Bingbing, et al.
Published: (2024)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
by: Bai, Tian, et al.
Published: (2026)