Cover Image

The Euclidean $k$-Matching Problem is NP-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Díaz-Báñez, José-Miguel, Fabila-Monroy, Ruy, Higes-López, José-Manuel, Marín, Nestaly, Pérez-Cutiño, Miguel-Angel, Pérez-Lantero, Pablo
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Filming runners with drones is hard
by: Díaz-Báñez, José-Miguel, et al.
Published: (2024)

Optimal covering of rectangular grid graphs with tours of constrained length
by: Bereg, Sergey, et al.
Published: (2025)

Optimizing Line Segment Inspection with Limited-Range Drones
by: Díaz-Báñez, José-Miguel, et al.
Published: (2026)

Modeling energy collection with shortest paths in rectangular grids: an efficient algorithm for energy harvesting
by: Díaz-Bañez, José-Miguel, et al.
Published: (2025)

Matching random colored points with rectangles (Corrigendum)
by: Corujo, Josué, et al.
Published: (2025)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
by: Bartlmae, Simon, et al.
Published: (2024)

Maximum-Weight Two Boxes Symmetric Difference Problem
by: Goycoolea, José Fernández, et al.
Published: (2026)

On maximum-sum matchings of bichromatic points
by: Chacón-Rivera, Oscar, et al.
Published: (2024)

On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs
by: Fabila-Monroy, Ruy, et al.
Published: (2024)

Computing optimal trajectories for a tethered pursuer
by: Barrera-Vicent, Aurelio, et al.
Published: (2025)

An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets
by: Flores-Peñaloza, David, et al.
Published: (2024)

Detecting broken Absorber Tubes in CSP plants using intelligent sampling and dual loss
by: Pérez-Cutiño, Miguel Angel, et al.
Published: (2022)

Computing the EHZ capacity is NP-hard
by: Leipold, Karla, et al.
Published: (2024)

Optimal energy collection with rotational movements constraints in concentrated solar power plants
by: Díaz-Bañez, J. M., et al.
Published: (2024)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Embedding Graphs as Euclidean kNN-Graphs
by: Schibler, T., et al.
Published: (2025)

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
by: Emmerich, Michael T. M., et al.
Published: (2026)

On connections between k-coloring and Euclidean k-means
by: Aman, Enver, et al.
Published: (2024)

Witness Set: A Visibility Problem in $NP\cap XP$
by: Jana, Satyabrata, et al.
Published: (2026)

Euclidean k-center Fair Clusterings
by: Moritaka, Ayano, et al.
Published: (2025)

Maximum rectilinear convex subsets
by: González-Aguilar, Hernán, et al.
Published: (2019)

Euclidean Maximum Matchings in the Plane---Local to Global
by: Biniaz, Ahmad, et al.
Published: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
by: Wulf, Lasse
Published: (2025)

Crossing Number is NP-hard for Constant Path-width (and Tree-width)
by: Hliněný, Petr, et al.
Published: (2024)

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
by: Huang, Lingxiao, et al.
Published: (2022)

NP-hardness of SVP in Euclidean Space
by: Wan, Daqing
Published: (2026)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Solving Euclidean Problems by Isotropic Initialization
by: Yorov, Khusrav, et al.
Published: (2025)

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
by: Har-Peled, Sariel, et al.
Published: (2014)

The Point-Boundary Art Gallery Problem is $\exists\mathbb{R}$-hard
by: Stade, Jack
Published: (2022)

Non-Euclidean Erdős-Anning Theorems
by: Eppstein, David
Published: (2024)

Approximating Gromov-Hausdorff Distance in Euclidean Space
by: Majhi, Sushovan, et al.
Published: (2019)

Improved Wake-Up Time For Euclidean Freeze-Tag Problem
by: Alipour, Sharareh, et al.
Published: (2025)

Optimal Euclidean Tree Covers
by: Chang, Hsien-Chih, et al.
Published: (2024)

Searching in Euclidean Spaces with Predictions
by: Cabello, Sergio, et al.
Published: (2024)

Euclidean TSP in Narrow Strips
by: Alkema, Henk, et al.
Published: (2020)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

Geometric Bipartite Matching Based Exact Algorithms for Server Problems
by: Raghvendra, Sharath, et al.
Published: (2025)