?
Finding a subset of nonnegative vectors with a coordinatewise large sum
Discrete Mathematics. 2013. Vol. 313. No. 5. P. 622–625.
Bogdanov I., Chelnokov G. R.
Given a rational $a = p/q$ and $N$ nonnegative $d$-dimensional real vectors $u_1, \dots , u_N$ , we
show that it is always possible to choose $(d − 1) + \lceil(pN − d + 1)/q\rceil$ of them such that
their sum is (componentwise) at least $(p/q)(u_1 + \cdots + u_N )$. For fixed $d$ and $a$, this bound
is sharp if $N$ is large enough. The method of the proof uses Carathйodory’s theorem from
linear programming.
Language:
English
Jia J., Guan X., Pardalos P. M., Journal of Computational and Applied Mathematics 2026 Vol. 486 Article 117687
We study the restricted inverse optimal value problem on linear programming under weighted l1 norm (RIOVLP1). Given a linear programming problem (LP with a feasible solution x0 and a value K, we aim to adjust the cost vector c to such that x0 becomes an optimal solution of the problem (LP) whose objective value equals K. The objective function is to minimize the distance under weighted l1 norm. First, we reformulate ...
Added: April 10, 2026
Bogachev T., Kolesnikov A., Математические заметки 2023 Т. 114 № 2 С. 181–194
In this paper, we study the functional ΦΦ that arises in numerous economic applications, in particular, in the monopolist problem. A special feature of these problems is that the domains of such functionals are nonclassical (in our case, increasing convex functions). We use an appropriate minimax theorem to prove the duality relation for ΦΦ. In particular, an important ...
Added: September 5, 2023
Raayatpanah M. A., Khodayifar S., Weise T. et al., Journal of Combinatorial Optimization 2022 Vol. 44 No. 1 P. 242–268
In this paper, an extension of the minimum cost flow problem is considered in which multiple incommensurate weights are associated with each arc. In the minimum cost flow problem, flow is sent over the arcs of a graph from source nodes to sink nodes. The goal is to select a subgraph with minimum associated costs ...
Added: November 16, 2021
Kuznetsov V. O., Логистика и управление цепями поставок 2018 № 1 (84) С. 32–39
On the one hand, the relevance of this research is determined by an attempt of solving the problem of optimal inventory allocation, which can open the possibilities for increase in stock turnover. On the other hand, there was an attempt to extend the list of problems which can be solved by operations research methods. The ...
Added: November 29, 2018
Belenky A., Egorova L., , in: Optimization and Its Applications in Control and Data Sciences: In Honor of Boris T. Polyak’s 80th Birthday (Springer Optimization and Its Applications)Book 115.: Springer, 2016. P. 51–117.
The paper proposes two new approaches to designing efficient mathematical tools for quantitatively analyzing decision-making processes that small and medium price-taking traders undergo in forming and managing their portfolios of financial instruments traded in a stock exchange. Two mathematical models underlying these approaches are considered. If the trader can treat price changes for each financial ...
Added: October 10, 2016
Alexander S. Belenky, Bolkunov D. S., Energy Systems 2016 Vol. 7 No. 4 P. 663–698
Added: March 1, 2016
Alexander S. Belenky, Energy Systems 2015 Vol. 6 No. 2 P. 291–308
A game with a finite (more than three) number of players on a polyhedron of connected player strategies is studied. This game describes the interaction among (a) the base load power plant (the generator), (b) all the large customers of a regional electrical grid that receive electric energy from the generator, as well as from ...
Added: July 8, 2015
Aleskerov F. T., Piontkovski D., Ersel H., Dordrecht, L., Heidelberg, NY: Springer, 2011.
The main aim of the book is, naturally, to give students the fundamental notions and instruments in linear algebra. Linearity is the main assumption used in all fieldsof science. It gives a first approximation to any problem under study and is widely used in economics and other social sciences. One may wonder why we decided ...
Added: September 11, 2011
Fana N., Zhengb Q. P., Pardalos P. M., Theoretical Computer Science 2012 Vol. 447 P. 53–61
The graph partitioning problem is to partition the vertex set of a graph into a number of nonempty subsets so that the total weight of edges connecting distinct subsets is minimized. Previous research requires the input of cardinalities of subsets or the number of subsets for equipartition. In this paper, the problem is formulated as ...
Added: December 31, 2012