The Fréchet Contingency Array Problem is Max-Plus Linear

2009/04/15 by Laurent Truffet, Truffet, Laurent
Computer Science · Mathematics · #Algorithms and Data Compression #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #math.OC #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0904.2244

arxiv created 2009/04/15 · openalex publication_date 2009/04/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we show that the so-called array Fréchet problem in Probability/Statistics is (max, +)-linear. The upper bound of Fréchet is obtained using simple arguments from residuation theory and lattice distributivity. The lower bound is obtained as a loop invariant of a greedy algorithm. The algorithm is based on the max-plus linearity of the Fréchet problem and the Monge property of bivariate distribution.

Citations

• The Maslov dequantization, idempotent and tropical mathematics: A brief introduction

Related

• Convex geometry of max-stable distributions
• Polynomial Time Relatively Computable Triangular Arrays in a Multinomial Setting
• Characterization of multivariate Bernoulli distributions with given margins
• Rates of convergence towards the Fréchet distribution
• Extended Convolution Bounds on the Fréchet Problem: Robust Risk Aggregation and Risk Sharing