Image de couverture de livre

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Emmerich, Michael T. M., Pereverdieva, Ksenia, Deutz, André H.
Format:	Preprint
Publié:	2026
Sujets:	Computational Geometry Computational Complexity Optimization and Control 68Q17, 90C27, 05C69 F.2.2; F.1.3
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
par: Emmerich, Michael T. M., et autres
Publié: (2026)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
par: Emmerich, Michael T. M., et autres
Publié: (2026)

Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
par: Emmerich, Michael T. M.
Publié: (2026)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
par: Lagerkvist, Victor, et autres
Publié: (2026)

The n-vehicle exploration problem is NP-complete
par: Cui, Jinchuan, et autres
Publié: (2023)

NP-hardness of p-adic linear regression
par: Baker, Gregory D.
Publié: (2026)

Exact Uniform L1 Spacing for Solow-Polasky Diversity on Lines and Ordered Pareto Fronts
par: Emmerich, Michael T. M., et autres
Publié: (2026)

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

Mim-Width is paraNP-complete
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
par: Lobe, Elisabeth, et autres
Publié: (2021)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
par: Eua-anant, Pakapim, et autres
Publié: (2025)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
par: Jansen, Klaus, et autres
Publié: (2024)

The Gallai Vertex Problem is $Θ_2^p$-Complete
par: Nikabadi, Amir, et autres
Publié: (2026)

NP-hard problems are not in BQP
par: Czerwinski, Reiner
Publié: (2023)

Cluster deletion and clique partitioning in graphs with bounded clique number
par: Galesi, Nicola, et autres
Publié: (2025)

Steiner Tree Parameterized by Multiway Cut and Even Less
par: Jansen, Bart M. P., et autres
Publié: (2024)

Robust Extensible Bin Packing and Revisiting the Convex Knapsack Problem
par: Goldberg, Noam, et autres
Publié: (2025)

On weighted graph separation problems and flow-augmentation
par: Kim, Eun Jung, et autres
Publié: (2022)

Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
par: Bärligea, Adelina, et autres
Publié: (2025)

DAG Scheduling in the BSP Model
par: Papp, Pál András, et autres
Publié: (2023)

Stiefel optimization is NP-hard
par: Lai, Zehua, et autres
Publié: (2025)

Dataless Neural Networks for Resource-Constrained Project Scheduling
par: Bara, Marc
Publié: (2025)

Modern column generation for estimating single- and multi-purchase ranked list choice models
par: Costa, Luciano, et autres
Publié: (2026)

Evolomino is NP-complete
par: Nikolaev, Andrei V.
Publié: (2025)

Locality, Consistency, and the Tractability Frontier
par: Simas, Tristan
Publié: (2026)

The Optimizer Quotient and the Certification Trilemma
par: Simas, Tristan
Publié: (2026)

A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems
par: Duchnowski, Alex, et autres
Publié: (2025)

Investigating Techniques to Optimise the Layout of Turbines in a Windfarm using a Quantum Computer
par: Hancock, James, et autres
Publié: (2023)

Investigating methods to solve large windfarm optimization problems with a minimum number of qubits using circuit-based quantum computers
par: Hancock, James, et autres
Publié: (2025)

On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
par: Ameli, Afrouz Jabal, et autres
Publié: (2024)

Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
par: Nederlof, Jesper, et autres
Publié: (2023)

The Word Problem for Products of Symmetric Groups
par: Simon, Hans U.
Publié: (2025)

On Small-depth Frege Proofs for PHP
par: Håstad, Johan
Publié: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
par: Levin, Leonid A.
Publié: (2022)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
par: Xia, Mingji
Publié: (2026)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
par: Phillips, Reed
Publié: (2026)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
par: Kiatchaipipat, Nattapol, et autres
Publié: (2025)

Quantum Similarity-Driven QUBO Framework for Multi-Period Supply Chain Allocation using Time-Multiplexed Coherent Ising Machines and Simulated Quantum Annealing
par: Ubale, Rushikesh, et autres
Publié: (2025)

Counting Martingales for Measure and Dimension in Complexity Classes
par: Hitchcock, John M., et autres
Publié: (2025)

Block Stacking, Airplane Refueling, and Robust Appointment Scheduling
par: Gmeiner, Simon, et autres
Publié: (2026)