Cover Image

Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Emmerich, Michael T. M.
Format:	Preprint
Published:	2026
Subjects:	Computational Geometry Data Structures and Algorithms Optimization and Control 68U05, 68Q25, 68W40, 90C27, 90C39 F.2.2; G.2.1; G.1.6
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Extending Exact Integrality Gap Computations for the Metric TSP
by: Cook, William, 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)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
by: Li, Shisheng
Published: (2026)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
by: Feldman, Moran, et al.
Published: (2026)

Modern column generation for estimating single- and multi-purchase ranked list choice models
by: Costa, Luciano, et al.
Published: (2026)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
by: Michel, Stefan
Published: (2025)

Approximation algorithms for the prize-collecting rural postman problem
by: Li, Hong, et al.
Published: (2026)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
by: Buchbinder, Niv, et al.
Published: (2024)

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
by: Foos, Josefine, et al.
Published: (2023)

An improved approximation algorithm for k-Median
by: Young, Neal E.
Published: (2025)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

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

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

The Subspace Flatness Conjecture and Faster Integer Programming
by: Reis, Victor, et al.
Published: (2023)

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

A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
by: Ryabchenko, Alexander, et al.
Published: (2026)

Compressed and Sparse Models for Non-Convex Decentralized Learning
by: Campbell, Andrew, et al.
Published: (2023)

Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN
by: Ali, Alejandro Mata
Published: (2025)

Incremental-Decremental Maximization
by: Disser, Yann, et al.
Published: (2025)

From approximate to exact integer programming
by: Dadush, Daniel, et al.
Published: (2022)

Polyhedral approach to weighted connected matchings in general graphs
by: Samer, Phillippe, et al.
Published: (2023)

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
by: Emmerich, Michael T. M., et al.
Published: (2026)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

Communication Compression for Distributed Learning without Control Variates
by: Ortega, Tomas, et al.
Published: (2024)

Communication Compression for Distributed Learning with Aggregate and Server-Guided Feedback
by: Ortega, Tomas, et al.
Published: (2025)

Quantized and Asynchronous Federated Learning
by: Ortega, Tomas, et al.
Published: (2024)

Decentralized Parameter-Free Online Learning with Compressed Gossip
by: Ortega, Tomas, et al.
Published: (2026)

Decentralized Parameter-Free Online Learning
by: Ortega, Tomas, et al.
Published: (2025)

Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination
by: Fang, Xiaolei, et al.
Published: (2026)

Quantum walk informed variational algorithm design
by: Matwiejew, Edric, et al.
Published: (2024)

Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA
by: Ali, Alejandro Mata
Published: (2025)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
by: Alimi, Morteza, et al.
Published: (2025)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
by: Liu, Bowen
Published: (2025)

Investigating Techniques to Optimise the Layout of Turbines in a Windfarm using a Quantum Computer
by: Hancock, James, et al.
Published: (2023)

Investigating methods to solve large windfarm optimization problems with a minimum number of qubits using circuit-based quantum computers
by: Hancock, James, et al.
Published: (2025)

Socio-cognitive agent-oriented evolutionary algorithm with trust-based optimization
by: Urbańczyk, Aleksandra, et al.
Published: (2025)