Extremal circular permutations with concave functions
This paper deals with the problem of arranging a set \(S= \{a_1, a_2,\dots, a_n\}\) with \(a_1< a_2<\cdots< a_n\) of \(n\) reals in a circular arrangement to maximize a function based on the differences between neighboring elements, a problem which was studied by \textit{C.-C. Chao} and \textit{W.-Q. Liang} [Eur. J. Comb. 13, No. 5, 325--334 (1992; Zbl 0769.05002)], and this paper seeks to provide a correction to Chao and Liang's paper. Let the set of all permutations of \(S\) be debited by \(A\), and let \(f:\mathbb{R}^+\to \mathbb{R}^+\) be a strictly increasing and concave function. Let \(\sum^n_{i=1} f|\alpha_1- \alpha_{i+1}|\) be denoted by \(D_f(A_1)\) where \(A_1= (\alpha_1,\alpha_2,\dots, \alpha_n)\) is an element of \(A\) with \(\alpha_{n+1}= \alpha_1\). In this paper the problem of the combinatorial optimization of \[ L_f:\text{ Find }\widehat A\in A\text{ such that }Df(\widehat A)= \max_{\widehat A_1\in\widehat A}\, D_f(A_1) \] is considered. The main result is as follows: Let \(f: \mathbb{R}^+\to\mathbb{R}^+\) be strictly concave and increasing. Let \(\{a_1,a_2,\dots, a_n\}\) be a set of distinct reals such that \(n\) is odd. Then the solution for \(L_f\) is given by: \[ \widehat A= a_1, a_{1+{n+1\over 2}}, a_{1+2{n+1\over 2}},\dots, a_{1+(n- 1){n+1\over 2}}. \]
- Arranging \(n\) distinct numbers on a line or a circle to reach extreme total variations
- Bounds on the minimum of convex functions on Euclidean combinatorial sets
- Three-dimensional axial assignment problems with decomposable cost coefficients
- scientific article; zbMATH DE number 3906215
- Generalized Rearrangement Inequalities
- Extremal properties of nondifferentiable convex functions on euclidean sets of combinations with repetitions
- scientific article; zbMATH DE number 706834
- On a Markov Decision Process problem involving the Maximum of the Difference between two functions: Technical Note
- scientific article; zbMATH DE number 3932799
- scientific article; zbMATH DE number 17642
This page was built for publication: Extremal circular permutations with concave functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1883620)
