Bounds on polarization problems on compact sets via mixed integer programming

Rolfes J, Schüler R, Zimmermann M (2024)

Publication Language: English

Publication Status: Accepted

Publication Type: Journal article, Original article

Future Publication Type: Journal article

Publication year: 2024

Journal

Discrete & Computational Geometry Springer Verlag (Germany)

URI: https://link.springer.com/article/10.1007/s00454-024-00635-z

DOI: 10.1007/s00454-024-00635-z

Open Access Link: https://link.springer.com/article/10.1007/s00454-024-00635-z

Abstract

Finding point configurations, that yield the maximum polarization (Chebyshev constant) is gaining interest in the field of geometric optimization. In the present article, we study the problem of unconstrained maximum polarization on compact sets. In particular, we discuss necessary conditions for local optimality, such as that a locally optimal configuration is always contained in the convex hull of the respective darkest points. Building on this, we propose two sequences of mixed-integer linear programs in order to compute lower and upper bounds on the maximal polarization, where the lower bound is constructive. Moreover, we prove the convergence of these sequences towards the maximal polarization.

Authors with CRIS profile

Jan Rolfes Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

Universität zu Köln DE Germany (DE) Universität Rostock DE Germany (DE)

How to cite

APA:

Rolfes, J., Schüler, R., & Zimmermann, M. (2024). Bounds on polarization problems on compact sets via mixed integer programming. Discrete & Computational Geometry. https://doi.org/10.1007/s00454-024-00635-z

MLA:

Rolfes, Jan, Robert Schüler, and Marc Zimmermann. "Bounds on polarization problems on compact sets via mixed integer programming." Discrete & Computational Geometry (2024).

BibTeX: Download