?
Calculating the minimal fraction of thepopular vote to win the U.S. Presidency in the electoral college
Computers & Mathematics with Applications. 2005. Vol. 50. No. 5-6. P. 783–802.
As is known, in U.S. presidential elections, all 50 states and the District of Columbi(DC) award their electoral votes to (the electors of) U.S. presidential candidates based on the popular vote received by (the electors of) the candidates there (although two different schemes of awarding the electoral votes are currently applied in the U.S.). For each particular (expected or actual) voter turnout in each of the states and in the District of Columbia, one may need to calculate the minimal fraction of the nationwide popular vote that secures the winning of the U.S. Presidency in the Electoral College. It is shown that this fraction can be found from solutions to certain integer linear programming problems.
Gribanov D., Khayaleyev T., Cherniavskii M. et al., , in: ESA'2026: Proceedings of the 34th Annual European Symposium on Algorithms.: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2026. Ch. 388 P. 25:1–25:22.
We study the standard-form ILP problem max{c⊤x:Ax=b,x∈Zn≥0}, where A∈Zk×n has full row rank. We obtain refined FPT algorithms parameterized by k and Δ, the maximum absolute value of a k×k minor of A. Our approach combines discrepancy-based dynamic programming with matrix discrepancy bounds in Komlós' setting. Let κk denote the maximum discrepancy over all matrices with k columns whose columns have Euclidean norm at most 1. Up to polynomial ...
Added: August 24, 2026
Dmitry V. Gribanov, Dmitry S. Malyshev, Pardalos P. M. et al., Computational Optimization and Applications 2025 Vol. 92 P. 811–861
In this paper, we consider the counting function $\QEnum(y) = |\PC_{y} \cap \ZZ^{n_x}|$ for a parametric polyhedron $\PC_{y} = \{ x \in \RR^{n_x} \colon A x \leq b + B y\}$, where $y \in \RR^{n_y}$. We give a new representation of $\QEnum(y)$, called a \emph{piece-wise step-polynomial with periodic coefficients}, which is a generalization of piece-wise ...
Added: December 6, 2024
Gribanov D., Malyshev D., Shumilov I., Operations Research Forum 2024 Vol. 5 Article 32
In our note, we present a very simple and short proof of a new interesting fact about
the faces of an integer hull of a given rational polyhedron. This fact has a complete
analog in linear programming theory and can be useful to establish new constructive
upper bounds on the number of vertices in an integer hull of ...
Added: April 4, 2024
Gribanov D., Shumilov I., Malyshev D. et al., Journal of Global Optimization 2024 Vol. 89 P. 1033–1067
In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P ∩ Zn , assuming that P is a polyhedron, defined by systems Ax ≤ b or Ax = b, x ≥ 0 with a sparse ...
Added: March 6, 2024
Vaskin I., Социологическое обозрение 2024 Т. 23 № 1 С. 107–134
The article analyses the socio-demographic and political recruitment factors for the Assembly of Experts of Iran from 1983-2024. The Assembly is an electoral college that has constitutional control over the Supreme Leader of Iran, but does not use its powers. The database comprises 446 observations related to 216 persons during 5 Assemblies since 1983. The ...
Added: September 18, 2023
Gribanov D., Malyshev D., Siberian Electronic Mathematical Reports 2022 Vol. 19 No. 2 P. 613–626
Let a polytope P be defined by a system Ax ≤ b. We consider the problem to count a number of integer points inside P, assuming that P is ∆-modular. The polytope P is ∆-modular if all the rank sub-determinants of A are bounded by ∆ in the absolute value. We present a new FPT-algorithm, ...
Added: September 19, 2022
Gribanov D., Shumilov I., Dmitry Malyshev et al., Journal of Global Optimization 2024 Vol. 88 P. 591–651
Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type $\max\{c^\top x \colon A x = b,\, x \in \ZZ^n_{\geq 0}\}$, where all the entries of $A,b,c$ are integer, parameterized by the number of rows of $A$ and $\|A\|_{\max}$. This class of problems is known under ...
Added: May 10, 2022
Belogaev A., Alexey Elokhin, Krasilov A. et al., IEEE Access 2020 Vol. 8 P. 169010–169023
Intelligent Transportation Systems (ITS) will become an essential part of every city in the near future. They should support various vehicle-to-everything (V2X) applications that improve road safety or even enable autonomous driving. Recently, the European Telecommunications Standards Institute (ETSI) introduced a multi-access (mobile) edge computing concept as a promising solution to satisfy the V2X delay ...
Added: September 18, 2020
Musatova E. G., Lazarev A. A., Ponomarev K. et al., IFAC-PapersOnLine 2016 Vol. 49 No. 12 P. 221–225
We consider a problem of the astronaut training scheduling. Each astronaut has his own set of tasks which should be performed with respect to resource and time constraints. The problem is to determine start moments for all considered tasks. For this issue a mathematical model based on integer linear programming is proposed. Computational results of ...
Added: October 31, 2016
Gribanov D., Malyshev D., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19–31
Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...
Added: October 20, 2016
Belenky A., М.: ЮНИТИ-ДАНА, 2016.
“How the U.S. President is elected” is the first book in Russian that narrates about the U.S. presidential election system, which is one of the most unique election systems in the world. The book is written in the form of questions and answers, and it acquaints the reader with all the stages of the process of ...
Added: October 11, 2016
Lazarev A. A., Musatova E. G., Управление большими системами: сборник трудов 2012 № 38 С. 161–169
We consider the problem of cars-to-train assignments, routing and scheduling, which is to minimize the weighted average time of transportation orders execution by consistently choosing the compound of trains, their routes from origins to destinations, and schedules. We offer the new integer problem settings to account for different cases of practical constraints. ...
Added: November 23, 2012
Belenky A., Dordrecht, L., Heidelberg, NY: Springer, 2012.
This is the first book on the U.S. presidential election system to analyze the basic principles underlying the design of the existing system and those at the heart of competing proposals for improving the system. The book discusses how the use of some election rules embedded in the U.S. Constitution and in the Presidential Succession ...
Added: September 25, 2012