### ?

## A Graphical Approach to Solve Combinatorial Problems: Algorithms and Some Computational Results

P. 403–408.

Lazarev A. A., Gafarov E., Werner F.

In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For some single machine scheduling problems, it is shown that the time complexity of the GrA is less than the time complexity of the standard DPA. Moreover, the average running time of the GrA is often essentially smaller. A GrA can also solve large-scale instances and instances, where the parameters are not integer. For some problems, GrA has a polynomial time complexity in contrast to a pseudo-polynomial complexity of a DPA.

### In book

Бухарест: IFAC Technical Committee, 2012.

Lazarev A. A., Werner F., Mathematical and Computer Modelling 2009 Vol. 49 No. 9-10 P. 2061–2072

The scheduling problem of minimizing total tardiness on a single machine is known to be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times p_j and the due dates d_j of the jobs are oppositely ordered: p_1 >= p_2>=...>=p_n and d_1. ...

Added: November 24, 2012

Andreev N. A., Mathematics 2019 Vol. 7 No. 12 P. 1147

We present a robust dynamic programming approach to the general portfolio selection problem in the presence of transaction costs and trading limits. We formulate the problem as a dynamic infinite game against nature and obtain the corresponding Bellman-Isaacs equation. Under~several additional assumptions, we get an alternative form of the equation, which is more feasible for ...

Added: October 30, 2019

Sotnikova S., Динамика сложных систем 2012 № 3 С. 84–87

In article is described designed programme complex of the physical processes modeling, which also allows to conduct the identification printed node parameters (the physical model). On printed node designed the on-board secondary power supply source is realized. For it are designed relationship interfaces of controlling program with the known program of modeling and optimization. ...

Added: December 5, 2014

Shirokova E., Евтушенко Л. Г., Laputenko A., , in: Proceedings 2021 IEEE East-West Design & Test Symposium (EWDTS). IEEE, 2021. P. 1–5.

Added: May 24, 2022

Springer, 2019.

16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, Proceedings ...

Added: October 26, 2021

Gafarov E., Lazarev A. A., Werner F., / Otto-von-Guericke Universitaet. 2010. No. 10.

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. An NP-hardness proof and a pseudo-polynomial time solution algorithm are proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted ...

Added: March 4, 2013

Guimarães R. R., Passos L., Filho R. H. et al., IEEE Network 2019 Vol. 33 No. 2 P. 126–131

Distinguishing outliers from normal data in wireless sensor networks has been a big challenge in the anomaly detection domain, mostly due to the nature of the anomalies, such as software or hardware failures, reading errors or malicious attacks, just to name a few. In this article, we introduce an anomaly detection-based OPF classifier in the ...

Added: December 19, 2018

Gafarov E., Lazarev A. A., Werner F., Mathematical Social Sciences 2011 No. 62 P. 7–13

We consider single machine scheduling problems with a non-renewable resource. These types of problems have not been intensively investigated in the literature so far. For several problems of these types with standard objective functions (namely the minimization of makespan, total tardiness, number of tardy jobs, total completion time and maximum lateness), we present some complexity ...

Added: November 24, 2012

Gourary M. M., Rusakov S. G., Ulyanov S. et al., , in: 2017 INTERNATIONAL SIBERIAN CONFERENCE ON CONTROL AND COMMUNICATIONS. Proceedings. IEEE, 2017. P. 1–4.

The optimization approach to design of linear voltage regulators for system on chip is proposed. The approach allows to find capacitances of a regulator under constraints on performance metrics. The optimization subsystem is described and an illustrative example is given. ...

Added: February 19, 2018

Lazarev A. A., Arkhipov D. I., , in: 28th Conference of the European Chapter on Combinatorial Optimization. Катания: University of Catania, 2015. P. 64.

The following classical NP-complete scheduling problem is considered. ...

Added: June 22, 2015

Kofanov Y. N., Sotnikova S., Rotkevich A. S. et al., , in: Proceedings of the 2018 IEEE International Conference "Quality Management, Transport and Information Security, Information Technologies" (IT&QM&IS). IEEE, 2018. P. 349–353.

The article presents a technique for investigating the electrical and thermal processes occurring in the receiving- computational units for unmanned aerial vehicles. A special feature of the technique is the consideration of random variance of technological parameters of materials and electrical parameters of electronic components. This technique provides for mutual phased electric modeling using SPICE ...

Added: November 19, 2018

Babenko M. A., Kociumaka T., Gawrychowski P. et al., , in: Lecture Notes in Computer ScienceVol. 8486: Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching. Springer, 2014. P. 30–39.

We revisit the problems of computing the maximal and the minimal non-empty suffixes of a substring of a longer text of length n, introduced by Babenko, Kolesnichenko and Starikovskaya [CPM’13]. For the minimal suffix problem we show that for any 1 ≤ τ ≤ logn there exists a linear-space data structure with(τ)query time and(nlogn/τ)preprocessing time. As a sample application, we show that ...

Added: June 24, 2014

Ермоленко Г. В., Ермоленко Б. В., Фетисова Ю. А., , in: 16th international multidisciplinary scientific geoconference SGEM 2016 Conference proceedingsVol. 3: Recycling, air pollution & climate change, modern energy and power sources. Book 4: Energy and clean technologies. Wien: [б.и.], 2016. P. 305–312.

The article is devoted to development of optimal design mathematical models for power systems using renewable energy sources (RES) on the stage of pre-investment feasibility study. Economic and social practicability of the carbon-free energy sector development in Russia is confirmed by calculated data of renewable energy sources potentials such as fuel, heat and power, resource ...

Added: February 17, 2017

Pham Cong T., Копылов А. В., Computer Optics 2018 P. 1–8

We consider here image denoising procedures, based on computationally effective tree-serial parametric dynamic programming procedures, different representations of an image lattice by the set of acyclic graphs and non-convex regularization of a new type which allows to flexibly set a priori preferences. Experimental results in image denoising, as well as comparison with related methods, are ...

Added: July 21, 2018

Lazarev A. A., , in: European Chapter on Combinatorial Optimization (ECCO 2009). Jerusalem: [б.и.], 2009. P. 13–13.

In this paper, for $NP$-hardness single and multi-machine scheduling problems with the criterion of minimization maximum lateness the metrics $\rho$ has been used. We consider some approaches finding of the approximate solution for the problems. The idea of approaches consists in construction to a initial instance $A$ such instance $B$ (with the same number of ...

Added: March 4, 2013

Bochkarev A. A., Бочкарев П. А., М.: Юрайт, 2017.

The last years are characterized by increase of interest in the logistics of city transport systems (city logistics) representing the complex of logistic decisions, actions and processes. In the manual methodological bases of control of regional transport logistic systems of city level are explained. The main attention is paid to the theory and methodology of ...

Added: October 31, 2017

Gafarov E., Lazarev A. A., Information Processing Letters 2012 Т. 112 № 3 С. 72–76

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function.
A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new
graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number
of tardy jobs on a single ...

Added: November 24, 2012

Kvaratskhelia A., Lazarev A. A., , in: Multidisciplinary International Conference on Scheduling: Theory and Application, Paris, France, 2009. Dublin: [б.и.], 2009. P. 68–76.

In this paper, we consider the minimizing total weighted completion time inpreemptive equal-length job with release dates scheduling problem on a single machine. Before this paper the problem is known to be open. Here, we present a polynomial timealgorithm that solves the problem with O(n^7) operations. ...

Added: March 4, 2013

Gafarov E., Lazarev A. A., Werner F., Annals of Operations Research 2012 Vol. 196 No. 1 P. 247–261

We consider the problem of maximizing total tardiness on a single machine, where the first job starts at time zero and idle times between the processing of jobs are not allowed.We present a modification of an exact pseudo-polynomial algorithm based on a graphical approach, which has a polynomial running time. This result settles the complexity ...

Added: November 24, 2012

Springer, 2014.

This book constitutes the thoroughly refereed post-conference proceedings of the 8th International Conference on Learning and Optimization, LION 8, which was held in Gainesville, FL, USA, in February 2014. The 33 contributions presented were carefully reviewed and selected for inclusion in this book. A large variety of topics are covered, such as algorithm configuration; multiobjective ...

Added: September 15, 2014

Lazarev A. A., Журнал вычислительной математики и математической физики 2007 Т. 47 № 6 С. 1087–1099

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding ...

Added: November 23, 2012

Popkov Y., Dubnov Y. A., Popkov A. Y., Automation and Remote Control 2018 Vol. 79 No. 11 P. 2038–2051

The direct and inverse projections (DIP) method was proposed to reduce the feature space to the given dimensions oriented to the problems of randomized machine learning and based on the procedure of “direct” and “inverse” design. The “projector” matrices are determined by maximizing the relative entropy. It is suggested to estimate the information losses by ...

Added: February 12, 2019

Babenko M. A., Goldberg A. V., Gupta A. ,. et al., ACM Transactions on Algorithms 2016 Vol. 13 No. 1 P. 16:1–16:17

We consider the hub label optimization problem, which arises in designing fast preprocessing-based shortest- path algorithms. We give O(log n)-approximation algorithms for the objectives of minimizing the maximum label size (l∞-norm) and simultaneously minimizing a constant number of lp-norms. Prior to this, an O(log n)- approximation algorithm was known [Cohen et al. 2003] only for ...

Added: January 12, 2017

Архипов Д.И. Д. И., Werner F. F., Optimization Letters, Springer Berlin Heidelberg, Berlin 2017 Vol. V.11 No. 1 P. 165–177

The following special case of the classical NP-hard scheduling problem 1|r_j |Lmax is considered. There is a set of jobs N = {1, 2, . . . , n} with identical processing times p_j = p for all jobs j ∈ N. All jobs have to be processed on a single machine. The optimization criterion ...

Added: October 20, 2017