Optimal Algorithms for Solution of Convex Combinations Problems

Author : A. A. Kolpakov, A. G. Kolpakov

Abstract :We consider the convex combinations problem (CCP), which is formulated as follows: It is required describe the set  (x) of all coefficients of convex combinations of the given points {xi, i=1,...,n}Rk that yield the given point xRk. Using specific of the CCP, we develop an effective method for solution this problem. In particular, the method developed is optimal with probability one. We also consider the discrete convex combinations problem (DCCP), which is formulated as follows: It is required solve the CCP under the additional condition that the coefficients of the convex combinations take value from a given finite set.

Keywords :Convex combinations, discrete optimization, probability, Rⁿ space, mathematical modeling, linear algebra, algorithmic solution, computational geometry

Conference Name :International Conference on Innovations in Computing (ICIIC-24)

Conference Place Antalya, Turkey

Conference Date 12th Sep 2024