Cover Image

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Emmerich, Michael T. M., Pereverdieva, Ksenia, Deutz, André H.
Format:	Preprint
Published:	2026
Subjects:	Computational Geometry Computational Complexity Information Theory Optimization and Control 68Q17, 90C27, 05C69 F.2.2; F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
by: Emmerich, Michael T. M., et al.
Published: (2026)

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

The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
by: Lobe, Elisabeth, et al.
Published: (2021)

Exact Uniform L1 Spacing for Solow-Polasky Diversity on Lines and Ordered Pareto Fronts
by: Emmerich, Michael T. M., et al.
Published: (2026)

DAG Scheduling in the BSP Model
by: Papp, Pál András, et al.
Published: (2023)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

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

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Quantum Time-Space Tradeoffs for Matrix Problems
by: Beame, Paul, et al.
Published: (2024)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

Quoridor is PSPACE-Complete
by: Drop, Marius, et al.
Published: (2026)

The Computational Complexity of Variational Inequalities and Applications in Game Theory
by: Kapron, Bruce M., et al.
Published: (2024)

The Gallai Vertex Problem is $Θ_2^p$-Complete
by: Nikabadi, Amir, et al.
Published: (2026)

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

The Polynomial Hierarchy does not collapse
by: Czerwinski, Reiner
Published: (2024)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
by: Philip, Geevarghese, et al.
Published: (2026)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

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

Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
by: Lubiw, Anna, et al.
Published: (2025)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2024)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

P vs NP Problem in Portfolio Optimization: Integrating the Markowitz-CAPM Framework with Cardinality Constraints and Black-Scholes Derivative Pricing
by: Gondauri, Davit
Published: (2026)

Robust Extensible Bin Packing and Revisiting the Convex Knapsack Problem
by: Goldberg, Noam, et al.
Published: (2025)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
by: Bärligea, Adelina, et al.
Published: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)