?
An FPTAS for the Δ-Modular Multidimensional Knapsack Problem
P. 79–95.
Springer, 2025.
This book celebrates the remarkable contributions of Panos M. Pardalos, offering a comprehensive collection of 20 rigorously peer-reviewed articles that span the breadth of his research interests. From deterministic and stochastic global optimization to combinatorial optimization, this volume provides insights into solving modern applied problems in planning theory, support vector machines, data mining, supply chain ...
Added: April 29, 2025
Lazarev A. A., Lemtyuzhnikova D. V., Somov M. L., Mathematics 2022 Vol. 10 No. 5 P. 1–18
This paper is aimed at the problem of scheduling surgeries in operating rooms. To solve this problem, we suggest using some variation of the bin packing problem. The model is based on the actual operation of 10 operating rooms, each of which belongs to a specific department of the hospital. Departments are unevenly loaded, so ...
Added: December 5, 2022
Omrani H., Oveysi Z., Emrouznejad A. et al., Journal of the Operational Research Society 2023 Vol. 74 No. 4 P. 1150–1165
Conventional DEA performs like a “black box” and provides no information about sub-processes. In some cases, such as banks, providing services is made up of interactive and interdependent processes. Also, in real world applications, inputs could be shared among these sub-processes. Moreover, due to the characteristics of some variables, such as number of employees, only integer values could be assigned to ...
Added: September 3, 2022
Gribanov D., Zolotykh N., Optimization Letters 2022 Vol. 16 No. 7 P. 1991–2018
Let a polyhedron $P$ be defined by one of the following ways:
\begin{enumerate}
\item[(i)] $P = \{x \in \RR^n \colon A x \leq b\}$, where $A \in \ZZ^{(n+k) \times n}$, $b \in \ZZ^{(n+k)}$ and $\rank A = n$,
\item[(ii)] $P = \{x \in \RR_+^n \colon A x = b\}$, where $A \in \ZZ^{k \times n}$, $b \in \ZZ^{k}$ ...
Added: October 29, 2021
Cham: Springer, 2021.
This book constitutes the proceedings of the 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021, held in Irkutsk, Russia, in July 2021.
The 29 full papers and 1 short paper presented in this volume were carefully reviewed and selected from 102 submissions. Additionally, 2 full invited papers are presented in the volume. ...
Added: July 8, 2021
Чирков А. Ю., Gribanov D., Zolotykh N., , in: Mathematical Optimization Theory and Operations Research, 19th International Conference, MOTOR 2020, Novosibirsk, Russia, July 6–10, 2020, (Т. 12095).: Cham: Springer, 2020. P. 16–22.
We study the proximity of the optimal value of the m-dimensional knapsack problem to the optimal value of that problem with the additional restriction that only one type of items is allowed to include in the solution. We derive exact and asymptotic formulas for the precision of such approximation, i.e. for the infinum of the ratio ...
Added: September 15, 2020
Lazarev A. A., Lemtyuzhnikova D., Werner F., Applied Mathematical Modelling 2021 Vol. 89 No. 2 P. 1163–1176
NP -hard scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness, are considered. For such problems, a metric which delivers an upper bound on the absolute error of the objective function value is introduced. Taking the given instance of some problem and using the introduced metric, the nearest instance is deter- ...
Added: September 5, 2020
Springer, 2019.
In this paper, we study the Maximum Happy Vertices and the Maximum Happy Edges problems (MHV and MHE for short). Very recently, the problems attracted a lot of attention and were studied in Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17. Main focus of our work is lower bounds on the computational complexity ...
Added: October 29, 2019
Khachay M., Khachay M., Pardalos P., Springer, 2019.
This volume contains the refereed proceedings of the 18th international conference on Mathematical Optimization Theory and Operations Research (MOTOR 2019)1 held during July 8–12, 2019, near Ekaterinburg, Russia. The conference brings together a wide research community in the fields of mathematical programming and global optimization, discrete optimization, complexity theory and combinatorial algorithms, optimal control and games, and their applications in relevant ...
Added: October 24, 2019
Aldunin D. A., Fedin G., Информационные технологии 2019 Т. 25 № 4 С. 250–256
Distant learning has weaknesses related to missing tutor and kind of autodidacticism of the process, which may cause learner’s frustration in uncertain situations and force him or her to drop the learning course. Inasmuch as it is very important to help learner to select a set of needed courses, the article deals with the task ...
Added: September 18, 2019
Veselov S. I., Gribanov D., Malyshev D., Moscow University Computational Mathematics and Cybernetics 2019 Vol. 43 No. 1 P. 1–11
The problem of computing the width of simplices generated by the convex hull of their integer vertices is considered. An FPT algorithm, in which the parameter is the maximum absolute value of the rank minors of the matrix consisting from the simplex vertices, is presented. ...
Added: April 22, 2019
Gribanov D., , in: Computational Aspects and Applications in Large-Scale Networks. Springer Proceedings in Mathematics & StatisticsVol. 247.: Springer, 2018. P. 19–35.
In this paper, we present FPT algorithms for special cases of the shortest vector problem (SVP) and the integer linear programming problem (ILP), when matrices included in the problems’ formulations are near square. The main parameter is the maximal absolute value of rank minors of matrices included in the problem formulation. Additionally, we present FPT ...
Added: February 17, 2019
Bliznets Ivan, Cygan M., Komosa P. et al., ACM Transactions on Computation Theory 2018 Vol. 10 No. 2 P. 1–32
The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it H-free—that is, not containing H as an induced subgraph. The H-free Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of ...
Added: October 30, 2018
Springer, 2018.
This book constitutes the refereed post-conference proceedings of the 29th International Workshop on Combinatorial Algorithms, IWOCA 2018, held in Singapore, Singapore, in July 2018. The 31 regular papers presented in this volume were carefully reviewed and selected from 69 submissions. They cover diverse areas of combinatorical algorithms, complexity theory, graph theory and combinatorics, combinatorial optimization, ...
Added: October 23, 2018
Springer, 2018.
This book presents open optimization problems in graph theory and networks. Each chapter reflects developments in theory and applications based on Gregory Gutin’s fundamental contributions to advanced methods and techniques in combinatorial optimization.
Researchers, students, and engineers in computer science, big data, applied mathematics, operations research, algorithm design, artificial intelligence, software engineering, data analysis, industrial and ...
Added: October 10, 2018
Malyshev D., Gribanov D., Discrete Optimization 2018 Vol. 29 P. 103–110
We consider boolean linear programming formulations of the vertex and edge dominating set problems and prove their polynomial-time solvability for classes of graphs with constraint matrices having bounded minors in the absolute value. ...
Added: April 8, 2018
D. V. Gribanov, D.S. Malyshev, P. M. Pardalos et al., Journal of Combinatorial Optimization 2018 Vol. 35 No. 4 P. 1128–1146
In this paper, we present fixed-parameter tractable algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices included in the problems’ formulations are near square. The parameter is the maximum absolute value of the rank minors in the corresponding matrices. Additionally, we present fixed-parameter tractable algorithms ...
Added: February 19, 2018