Research Interests and Selected Publications:
Recently, a new inter-disciplinary research initiative
has emerged. This initiative is referred to as "Network Science" or
"Complex Network Analysis". It aims at understanding the structural properties
and the dynamics of various kinds of large scale networks in telecommunication (e.g., the Internet,
the web graph, peer-to-peer networks), social science (e.g., communities
of interest, advertisement, recommendation systems), bibliometrics (e.g., citations,
co-authors), biology (e.g., spread of an epidemic, protein-protein interactions),
and physics. The complex networks encountered in these areas share common properties
such as power law degree distribution, small average distances,
community structure, etc. It also appears that many general
questions/applications (centrality measures, e.g., PageRank, community detection,
epidemic spreading, motif counting, search) are common in various disciplines
which study networks.
Selected publications:
-
K. Avrachenkov, A. Kondratev, V. Mazalov and D. Rubanov,
Network partitioning algorithms
as cooperative games. Computational Social Networks, v.5(11), 2018.
-
K. Avrachenkov, N. Litvak, M. Sokol and D. Towsley:
Quick detection of nodes with large degrees.
Internet Mathematics, v.10(1-2), pp.1-19, 2014.
-
K. Avrachenkov, P. Goncalves, A. Mishenin and M. Sokol,
Generalized
optimization framework for graph-based semi-supervised learning.
Proceeding of SIAM Conference on Data Mining (SDM'2012), pp.966-974, 2012.
-
K. Avrachenkov, B. Ribeiro, and D. Towsley,
Improving random walk estimation accuracy with uniform restarts.
Proceedings of WAW 2010, December 2010, Also LNCS v.6516, pp.98-109, 2010.
-
K. Avrachenkov and D. Lebedev,
PageRank of scale free growing networks.
Internet Mathematics, v.3, no.2, pp.207-231, 2006, also
INRIA Research Report no. 5858, March 2006.
-
K. Avrachenkov, N. Litvak, D. Nemirovsky and N. Osipova,
Monte Carlo methods in PageRank computation:
When one iteration is sufficient. SIAM Journal on Numerical Analysis,
v.45, no.2, pp.890-904, 2007, also University of Twente Research Report,
February 2005.
-
K.E. Avrachenkov and N. Litvak,
The effect of new links on Google PageRank,
Stochastic Models, v.22, no.2, pp.319 - 331, 2006.
Also INRIA Research Report no. 5256, July 2004.
Back to the top
In Game Theory I am mostly interested in Markovian Competitive Decision Processes
(Stochastic Games), games with constraints and formation games. These types
of games find applications in wireless network power control, routing and
network formation.
Selected publications:
-
K. Avrachenkov, V. Ejov, J. Filar and A. Moghaddam,
Zero-sum stochastic games over the field of real algebraic numbers.
Dynamic Games and Applications, v.9(4), pp.1026-1041, 2019.
-
K. Avrachenkov and V. Singh,
Stochastic coalitional better-response dynamics for finite games
with application to network formation games.
Book chapter in
Multilevel Strategic Interaction Game Models for Complex Networks,
(eds.) E. Altman et al, pp.185-199, 2019.
-
K. Avrachenkov, J. Elias, F. Martignon, G. Neglia and L. Petrosyan,
Cooperative network design:
A Nash bargaining solution approach.
Computer Networks, v.83, pp.265-279, 2015.
-
K. Avrachenkov, L. Cottatellucci and L. Maggi,
Cooperative Markov decision processes:
Time consistency, greedy players satisfaction, and cooperation maintenance.
International Journal of Game Theory, v.42(1), pp.239-262, 2013.
-
K. Avrachenkov, L. Cottatellucci and L. Maggi,
Algorithms for uniform optimal strategies in
two-player zero-sum stochastic games with perfect information.
Operations Research Letters, v.40(1), pp.56-60, 2012.
-
E. Altman, K. Avrachenkov, N. Bonneau, M. Debbah, R. El-Azouzi, and D. Sadoc Menasche,
Constrained stochastic games in wireless networks.
Proceedings of IEEE GLOBECOM 2007.
-
E. Altman, K. Avrachenkov and A. Garnaev,
A jamming game in wireless networks
with transmission cost.
Proceedings of NETCOOP07, also in LNCS v.4465, pp.1-12, 2007.
Back to the top
In the Internet the reliable file transfer is done with the help of TCP/IP protocol.
For instance, Web browsing and FTP applications are based on TCP.
I am interested in the performance evaluation and optimization of computer networks
in terms of packet losses, packet delays, throughputs and latencies of file transfers.
Selected publications:
-
Z. Allybokus, K. Avrachenkov, J. Leguay and L. Maggi,
Multi-path alpha-fair resource allocation at scale in distributed software defined networks.
IEEE Journal on Selected Areas in Communications, v.36(12), pp.2655-2666, 2018.
-
K. Avrachenkov, A. Piunovskiy and Y. Zhang,
Impulsive control for G-AIMD dynamics with relaxed and hard constraints.
Proceedings of IEEE CDC 2018.
-
K. Avrachenkov, O. Habachi, A. Piunovskiy, and Y. Zhang,
Infinite horizon optimal impulsive control
with applications to Internet congestion control.
International Journal of Control, v.88(4), pp.703-716, 2015.
-
E. Altman, K. Avrachenkov and J. Goseling,
Distributed storage in the plane.
Proceedings of IFIP Networking 2014,
pp.1-9, June 2014.
-
K. Avrachenkov, U. Ayesta, and A. Piunovskiy,
Optimal choice of the buffer size
in the Internet routers,
Proceedings of IEEE CDC/ECC'05, pp.1143-1148, Seville, Spain,
December 2005.
-
E. Altman, K.E. Avrachenkov, and B. J. Prabhu,
Fairness in MIMD congestion control algorithms,
Proceedings of IEEE INFOCOM 2005, Miami,
March 2005. An extended version has appeared in
Telecommunication Systems, v.30(4), pp.387-415, 2005.
-
K.E. Avrachenkov, U. Ayesta, P. Brown, and E. Nyberg,
Differentiation between Short and Long TCP flows:
Predictability of the response time,
Proceedings of IEEE INFOCOM 2004, Hong Kong.
-
E. Altman, K.E. Avrachenkov and C. Barakat,
A stochastic model of TCP/IP with
stationary random losses,
ACM SIGCOMM 2000, Stockholm, Sweden. An extended version has appeared in
IEEE/ACM Trans. on Networking, v.13(2), April 2005, pp.356-369.
Back to the top
Analytic perturbation theory deals with a wide spectrum of mathematical
problems (e.g., the inversion of linear operators, the eigenvalue problems,
the systems of linear and nonlinear equations, mathematical programming)
whose data depend analytically on a "small" perturbation parameter.
There are at least two motivations to study this class of problems. Firstly,
it is often necessary to describe the behaviour of a problem solution with
respect to the change of its parameters. Secondly, admitting that we never
have precise data, it is of great importance to analyse the influence of
data perturbations. Sometimes even small perturbations of the data cause
dramatic changes in the properties of the problem. The latter case is called
the singular perturbation and it is of particular interest for my
research.
Ph.D. Thesis:
Book:
Selected publications:
-
K.E. Avrachenkov, R.S. Burachik, J.A. Filar and V. Gaitsgory,
Constraint augmentation in pseudo-singularly perturbed linear programs.
Mathematical Programming, v.132(1-2), pp.179-208, 2012.
-
K.E. Avrachenkov and M. Haviv,
Perturbation of null spaces with
application to the eigenvalue problem and generalized inverses,
Linear Algebra and its Applications, v.369, pp.1-25, 2003.
-
K.E. Avrachenkov and J.B. Lasserre,
Analytic perturbation of Sylvester and Lyapunov
matrix equations,
IEEE CDC 2000, Sydney, Australia, pp.1968-1973. An extended version is
appeared in IEEE Trans. Auto. Contr., v.47, no.7, pp.1116-1119, 2002.
-
J.A. Filar, E. Altman and K.E. Avrachenkov,
An asymptotic simplex
method for singularly perturbed linear programs,
Operations Research Letters, v.30, no.5, pp.295-307, October 2002.
-
K.E. Avrachenkov, M. Haviv and P.G. Howlett,
Inversion of analytic matrix functions
that are singular at the origin,
SIAM Journal on Matrix Analysis and Applications,
v.22, no.4, pp.1175-1189, 2001.
Back to the top
Here we apply the results of the general analytic perturbation theory
to singularly perturbed Markov chains and Markov decision processes.
The singularly perturbed Markov chain is an appropriate model for
a complex stochastic system which consists of several weakly
connected subsystems.
Selected publications:
-
K. Avrachenkov, J. Filar, V. Gaitsgory and A. Stillman,
Singularly perturbed linear programs and Markov decision processes.
Operations Research Letters, v.44(3), pp.297-301, 2016.
-
E. Altman, K.E. Avrachenkov, and R. Nunez-Queija,
Perturbation analysis for denumerable Markov chains
with application to queueing models,
Advances in Applied Probability, v.36, no.3, September 2004.
-
K.E. Avrachenkov and M. Haviv,
The first Laurent series coefficients
for singularly perturbed stochastic matrices,
Linear Algebra and its Applications, v.386, pp.243-259, July 2004.
-
K.E. Avrachenkov, J.A. Filar and M. Haviv,
Singular perturbations of Markov chains and decision processes. A Survey,
a chapter in Handbook of Markov Decision Processes: Methods and Applications,
(eds) E.A. Feinberg, A. Shwartz, v.40 in the series "International Series in
Operations Research and Management Science", Kluwer Academic Publishers,
pp.113-153, January 2002.
-
K.E. Avrachenkov,
Singularly perturbed finite Markov chains with general
ergodic structure,
in Discrete Event Systems: Analysis and Control, R. Boel and
G. Stremersch (Eds.), pp.429-432, Kluwer, 2000.
Back to the top
One can still obtain new interesting results for classical queueing models!
In particular, I am interested in processor sharing queues, retrial queues,
stochastic scheduling, multi-class queues and their applications in
communication systems.
Selected Publications:
-
K. Avrachenkov, E. Morozov and B. Steyaert,
Sufficient stability conditions
for multi-class constant retrial rate systems. Queueing Systems, v.82(1-2), pp.149-171, 2016.
-
K. Avrachenkov, P. Nain and U. Yechiali,
A retrial system with two input streams and two orbit queues.
Queueing Systems, v.77(1), pp.1-31, 2014.
-
K. Avrachenkov and U. Yechiali,
Retrial networks with finite buffers and their application
to Internet data traffic,
Probability in the Engineering and Informational Sciences, v.22, pp.519-536, 2008.
-
E. Altman, K. Avrachenkov and U. Ayesta,
A survey on discriminatory processor sharing
Queueing Systems, v.53(1-2), pp.53-63, 2006.
-
K. Avrachenkov, U. Ayesta, P. Brown, R. Nunez-Queija,
Discriminatory processor sharing revisited,
Proceedings of IEEE INFOCOM 2005, Miami, March 2005.
-
K. Avrachenkov, U. Ayesta and P. Brown,
Batch arrival processor-sharing with application
to multi-level processor sharing scheduling,
Queueing Systems, v.50(4), pp.459-480, 2005.
-
K.E. Avrachenkov, N.O. Vilchevsky, and G.L. Shevlyakov,
Priority queueing with finite buffer size
and randomized push-out mechanism,
Performance Evaluation, v.61(1), pp.1-16, 2005.
Back to the top
Iterative learning control (ILC) is designed
to improve the performance of a cyclic system.
The basic idea of ILC is to correct the control input
for the next cycle using the information about the error from
the current and previous cycles. If the unknown part of the
system can be represented as a regular perturbation, then we
propose to use fast convergent quasi-Newton-type methods.
However, if the unknown part of the system is a singular
perturbation, then we recommend to use robust methods based
on H-infinity controller design.
Selected publications:
-
K.E. Avrachenkov and R.W. Longman,
Iterative learning control for over-determined,
under-determined, and ill conditioned systems,
Int. J. Appl. Math. Comput. Sci., v.13, no.1, pp.113-122, 2003.
-
K.E. Avrachenkov, H.S.M. Beigi, and R.W. Longman,
Updating procedures for
iterative learning control in Hilbert space,
Intelligent Automation and Soft Computing,
v.8, no.2, pp.183-189, 2002.
-
K.E. Avrachenkov,
Iterative learning control based on quasi-Newton
methods, IEEE CDC'98 Proceedings, 1998.
-
K.E. Avrachenkov and A.A. Pervozvanskii,
Iterative learning control
for singularly perturbed systems, (extended version),
Proceedings of ILC workshop, 1998.
-
A.A. Pervozvanskii and K.E. Avrachenkov,
Learning control algorithms: convergence and robustness,
Proceedings of Australian Control Conference, pp.366-371,
October 1997.
Back to the top
Here is a collection of cute results that cannot be classified into
any of the above topics.
Selected publications:
-
K. Avrachenkov, A. Piunovskiy and Y. Zhang,
Hitting times in Markov chains with restart and their application to network centrality.
Methodology and Computing in Applied Probability, v.20(4), pp.1173-1188, 2018.
-
J.B. Lasserre and K.E. Avrachenkov,
Integration on a simplex:
The multi-dimensional version of \(\int_a^b x^p \, dx\)
Amer. Math. Monthly, v.108, pp.151-154, February 2001.
-
K.E. Avrachenkov and E. Sanchez,
Fuzzy Markov Chains and Decision-Making,
Fuzzy Optimization and Decision Making, v.1, no.2, pp.143-159, June 2002.
Back to the top
Back to the front page