Complexity of Local Search for Euclidean Clustering Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Manthey, Bodo, Morawietz, Nils, van Rhijn, Jesse, Sommer, Frank
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Counting Locally Optimal Tours in the TSP
von: Manthey, Bodo, et al.
Veröffentlicht: (2024)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
von: Grüttemeier, Niels, et al.
Veröffentlicht: (2025)

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
von: Balzereit, Kaja, et al.
Veröffentlicht: (2024)

Convergence and Running Time of Time-dependent Ant Colony Algorithms
von: Manthey, Bodo, et al.
Veröffentlicht: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Fine-Grained Complexity of Continuous Euclidean k-Center
von: Blank, Lotte, et al.
Veröffentlicht: (2026)

Clustering with Locally Bounded Ignorance
von: Garvardt, Jaroslav, et al.
Veröffentlicht: (2026)

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

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
von: Bai, Tian, et al.
Veröffentlicht: (2026)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
von: Lehner, Lisa, et al.
Veröffentlicht: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
von: Shih, Yu-Sheng, et al.
Veröffentlicht: (2026)

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

Graph Search Trees and the Intermezzo Problem
von: Beisegel, Jesse, et al.
Veröffentlicht: (2024)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
von: Zhang, Bingwei, et al.
Veröffentlicht: (2026)

Parameterized Complexity of Streaming Diameter and Connectivity Problems
von: Oostveen, Jelle J., et al.
Veröffentlicht: (2022)

Kernelization Complexity of Solution Discovery Problems
von: Grobler, Mario, et al.
Veröffentlicht: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

Exact and Approximate Algorithms for Polytree Learning
von: Harviainen, Juha, et al.
Veröffentlicht: (2026)

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
von: Komusiewicz, Christian, et al.
Veröffentlicht: (2026)

Towards Settling the Complexity of the Lettericity Problem
von: Grobler, Mario, et al.
Veröffentlicht: (2026)

Breadth-First Search Trees with Many or Few Leaves
von: Beisegel, Jesse, et al.
Veröffentlicht: (2026)

Cluster Editing on Cographs and Related Classes
von: Lafond, Manuel, et al.
Veröffentlicht: (2024)

Bandwidth Parameterized by Cluster Vertex Deletion Number
von: Gima, Tatsuya, et al.
Veröffentlicht: (2023)

The Complexity of Cluster Vertex Splitting and Company
von: Firbas, Alexander, et al.
Veröffentlicht: (2023)

Parameterized Algorithms for Editing to Uniform Cluster Graph
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2024)

Scheduling Problems with Constrained Rejections
von: Davies, Sami, et al.
Veröffentlicht: (2025)

Further Explanations on "SAT Requires Exhaustive Search"
von: Dong, Qingxiu, et al.
Veröffentlicht: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

On connections between k-coloring and Euclidean k-means
von: Aman, Enver, et al.
Veröffentlicht: (2024)

Near-Optimal Bounds for Parameterized Euclidean k-means
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)

String Consensus Problems with Swaps and Substitutions
von: Gabory, Estéban, et al.
Veröffentlicht: (2025)