?
Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions
Algorithmica (Германия). 2018. Vol. 80. No. 11. P. 3132-3157.
We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.
Publication based on the results of:
Afanasiev V., Semion A., Проблемы управления 2021 № 1 С. 24-35
A differential game of several players is considered as follows. One player (attacker) penetrates some space, and several other players (pursuers) appear simultaneously to intercept the attacker. Upon detecting the pursuers, the attacker tries to evade them. The dynamics of each player are described by a time-invariant linear system of a general type with scalar ...
Added: April 6, 2021
Gurvich V., Boros E., Milanič M. et al., Discrete Applied Mathematics 2018 Vol. 243 P. 21-38
We give an example of a three-person deterministic graphical game that has no Nash equilibrium in pure stationary strategies. The game has seven positions, four outcomes (a unique cycle and three terminal positions), and its normal form is of size 2×2×4 only. Thus, the example strengthens significantly the one obtained in 2014 by Gurvich and Oudalov; the ...
Added: October 10, 2018
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
Pardalos P. M., Maslov E. V., Lu Z. et al., Optimization Letters 2012 P. 1-10
In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two ...
Added: February 11, 2013
Malyshev D., Journal of Combinatorial Optimization 2017 Vol. 33 No. 3 P. 809-813
We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the ...
Added: March 17, 2016
Gasnikov A., Мендель М. А., Лагуновская А. А. et al., Труды Московского физико-технического института 2015 Т. 7 № 3
This paper describes some previously unexamined features in a multistage approach to transport modelling. The approach described is based on a theorem on the potentiality of the special population game that arises while the model of equilibrium fl ow distribution over paths and the model of correspondence formation are combined. ...
Added: October 23, 2015
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, 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
Gurvich V., Oudalov V., Discrete Applied Mathematics 2014 Vol. 167 P. 131-143
We study existence of Nash equilibria (NE) in pure stationary strategies in n-person positional games with no moves of chance, with perfect information, and with the mean or total effective cost function.
We construct a NE-free three-person game with positive local costs, thus disproving the conjecture suggested in Boros and Gurvich (2003). Still, the following four problems ...
Added: October 22, 2016
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
Lazarev A. A., Gafarov E., М. : Физический факультет МГУ, 2011
В данном учебном пособии приводятся базовые сведения о специальном разделе дискретной математики - Теории расписаний. Описаны этапы становления теории, свойства и классификации задач теории расписаний, методы их решения. На примерах классических задач представлены приемы доказательства их трудоемкости и алгоритмы решения. Учебное пособие основано на курсе лекций, читаемых в МФТИ, МГУ и ВШЭ, и предназначено для ...
Added: December 10, 2012
Berlin : Springer, 2014
This book constitutes the refereed proceedings of the 22st Annual European Symposium on Algorithms, ESA 2014, held in Wrocław, Poland, in September 2014, as part of ALGO 2014. The 69 revised full papers presented were carefully reviewed and selected from 269 initial submissions: 57 out of 221 in Track A, Design and Analysis, and 12 ...
Added: September 2, 2014
Gurvich V., Journal of Logic and Computation 2018 Vol. 28 No. 7 P. 1635-1646
For the classical backward induction algorithm, the input is an arbitrary n n -person positional game with perfect information modelled by a finite acyclic directed graph (digraph) and the output is a profile (x 1 ,…,x n ) (x1,…,xn) of pure positional strategies that form some special subgame perfect Nash equilibrium (NE). We extend this algorithm to work with digraphs that ...
Added: December 10, 2018
Lazarev A. A., Musatova E. G., Kvaratskhelia A. et al., М. : Физический факультет МГУ, 2012
Данное учебное пособие посвящено задачам теории расписаний, возникающим на транспорте. Представлены основы теории расписаний, а также способы построения моделей и методы решения задач управления транспортными системами. Изложенный материал предназначен для студентов и преподавателей вузов математических специальностей, специалистов в области управления и практиков, занимающихся решением задач планирования грузовых перевозок. ...
Added: December 10, 2012
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
Gurvich V., Koshevoy G., Discrete Applied Mathematics 2018 P. 1-15
Given two finite ordered sets A and B, let O=A×B denote the set of outcomes of the following game: Two players, Alice and Bob, have the sets of strategies X and Y that consist of all monotone non-decreasing mappings x:A→B and y:B→A, respectively. It is easily seen that each pair (x,y)∈X×Y produces at least one deal, that is, an outcome (a,b)∈O such that x(a)=b and y(b)=a. Denote by G(x,y)⊆O the set of all such deals related to (x,y). ...
Added: October 10, 2018
Toldova S., Azerkovich I., Гришина Ю. et al., / НИУ ВШЭ. Series WP BRP "Linguistics". 2015.
Building benchmark corpora in the domain of coreference and anaphora resolution is an important task for developing and evaluating NLP systems and models. Our study is aimed at assessing the feasibility of enhancing corpora with information about coreference relations. The annotation procedure includes identification of text segments that are subjects to annotation (markables), marking their ...
Added: December 15, 2015
Kiselyova N. N., Dudarev V.A., Korzhuev M. A., Inorganic Materials: Applied Research 2016 Vol. 7 No. 1 P. 34-39
A database (DB) on the bandgap of inorganic substances available via the Internet (http://bg.imetdb.ru) was developed for the information service of specialists in the sphere of inorganic chemistry and materials science. The DB is integrated with other information systems on the properties of inorganic substances and materials, which provides the search of a wide range ...
Added: February 23, 2016
Baibikova T., Domoratsky E., Вестник Московского финансово-юридического университета 2017 № 1 С. 200-206
Some questions of scientific visualization are under consideration in this paper. This article also discusses the peculiarities of application of cognitive computer graphics, singles out a range of tasks of scientific visualization. The paper gives a brief overview of modern support tools for program visualization, tendencies of their development and their main characteristics. A module ...
Added: June 10, 2017
Kalyagin V.A., Koldanov A.P., Koldanov P.A. et al., Physica A: Statistical Mechanics and its Applications 2014 Vol. 413 No. 1 P. 59-70
A general approach to measure statistical uncertainty of different filtration techniques for market network analysis is proposed. Two measures of statistical uncertainty are introduced and discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some important cases ...
Added: July 19, 2014
Karpov V. E., Karpova I. P., Procedia Engineering 2015 Vol. 100 P. 1459-1468
Work solutions are proposed for problems of leader definition and role distribution in homogeneous groups of robots. It is shown that transition from a swarm to a collective of robots with hierarchical organization is possible using exclusively local interaction. The local revoting algorithm is central to the procedure for choice of leader while redistribution of roles can ...
Added: March 14, 2015
Vishnekov A., Erokhin V., Ivanova E., Датчики и системы 2018 Т. 221 № 1 С. 18-24
The article discusses the recovery of distributed control systems of technical objects. The options for the design of subsystems recovery after hardware or software fault of the sensor system are investigated. The development of an integrated subsystems recovery is proposed on the basis of decision-making system to develop the most rational control actions by ...
Added: January 27, 2018
М. : National Instruments Russia, 2017
Содержание сборника составляют доклады с результатами оригинальных исследований и технических решений, ранее не публиковавшиеся. Мы надеемся, что предлагаемый сборник окажется полезным для специалистов, работающих в различных областях науки и техники, для широкого круга преподавателей, аспирантов и студентов ВУЗов, а также для преподавателей средних школ и технических колледжей. ...
Added: May 10, 2017
Furmanov K. K., Nikol'skii I. M., Computational Mathematics and Modeling 2016 Vol. 27 No. 2 P. 247-253
Added: December 22, 2016