Wyniki wyszukiwania - BazTech

1

A method of lower and upper solutions for control problems and application to a model of bone marrow transplantation

Parajdi Lorand Gabriel, Precup Radu, Haplea Ioan Ştefan

International Journal of Applied Mathematics and Computer Science

|

2023

|

Vol. 33, no. 3

409--418

EN

A lower and upper solution method is introduced for control problems related to abstract operator equations. The method is illustrated on a control problem for the Lotka-Volterra model with seasonal harvesting and applied to a control problem of cell evolution after bone marrow transplantation.

2

Worst-Case Analysis of an Approximation Algorithm for Single Machine Scheduling Problem

Grigoreva Natalia

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

221--225

EN

—The problem of minimizing the maximum delivery times while scheduling jobs on the single processor is a classical combinatorial optimization problem. This problem is denoted by 1|rj,qj|Cmax has many applications, and it is NP-hard in strong sense. The goal of this paper is to propose a new 3/2approximation algorithm, which runs in O(n log n) time. We proved that the bound of 3/2 is tight. To check the efficiency of the algorithm we tested it on random generated problems of up to 5000 jobs.

3

Two-center of the Convex Hull of a Point Set : Dynamic Model, and Restricted Streaming Model

Sadhu Sanjib, Roy Sasanka, Nandi Soumen, Maheshwari Anil, Nandy Subhas C.

Fundamenta Informaticae

|

2019

|

Vol. 164, nr 1

119--138

EN

In this paper, we consider the dynamic version of covering the convex hull of a point set P in ℝ2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2ropt at any query time, where ropt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O(log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2.

4

Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines

Pikies T., Kubale Marek

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2019

|

Vol. 67, nr 1

31--36

EN

The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|pj = 1, G = bisubquartic|Cmax. The second one is Algorithm 3 which is 4-approximate for the problem Qm|pj = 1, G = bisubquartic|ΣCj, where m ϵ {2, 3, 4}. The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.

5

An approximation algorithm for multi-unit auctions: numerical and subject experiments

Takahashi S., Izunaga Y., Watanabe N.

Operations Research and Decisions

|

2018

|

Vol. 28, No. 1

95--115

EN

In multi-unit auctions for a single item, the Vickrey–Clarke–Groves mechanism (VCG) attains allocative efficiency but suffers from its computational complexity. Takahashi and Shigeno thus proposed a greedy based approximation algorithm (GBA). In a subject experiment there was truly a difference in efficiency rate but no significant difference in seller’s revenue between GBA and VCG. It is not clear in theory whether each bidder will submit his or her true unit valuations in GBA. We show, however, that in a subject experiment there was no significant difference in the number of bids that obey “almost” truth-telling between GBA and VCG. As for individual bidding behavior, GBA and VCG show a sharp contrast when a human bidder competes against machine bidders; underbidding was observed in GBA, while overbidding was observed in VCG. Some results in a numerical experiment are also provided prior to reporting those observations.

6

Approximation of Reset Thresholds with Greedy Algorithms

Ananichev D. S., Gusev V. V.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

221--227

EN

The problem of approximate computation of reset thresholds of synchronizing automata has gained a lot of attention recently. We introduce a broad class of algorithms that compute reset words and analyze their approximation ratios. We present three series of automata that reveal inherent limitations of greedy strategies for approximation of reset thresholds.

7

An efficient connected dominating set algorithm in WSNs based on the induced tree of the crossed cube

Zhang J., Xu L., Zhou S. M., Wu W., Ye X.

International Journal of Applied Mathematics and Computer Science

|

2015

|

Vol. 25, no. 2

295--309

EN

The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms. In this paper, a novel algorithm based on the induced tree of the crossed cube (ITCC) is presented. The ITCC is to find a maximal independent set (MIS), which is based on building an induced tree of the crossed cube network, and then to connect the MIS nodes to form a CDS. The priority of an induced tree is determined according to a new parameter, the degree of the node in the square of a graph. This paper presents the proof that the ITCC generates a CDS with a lower approximation ratio. Furthermore, it is proved that the cardinality of the induced trees is a Fibonacci sequence, and an upper bound to the number of the dominating set is established. The simulations show that the algorithm provides the smallest CDS size compared with some other traditional algorithms.

8

Approximation algorithm supported on minimizing the Kullback-Leibler information divergence in some class of dynamical systems

Owedyk J., Mathia Z., Zarzycki H.

Biuletyn Naukowy Wrocławskiej Wyższej Szkoły Informatyki Stosowanej. Informatyka

|

2015

|

vol. 5

12--18

EN

In this work an algorithm is presented for creating approximate solutions in some class of dynamical systems describing the time evolution probability densities. The approximate solutions are obtained by minimizing Kullback- Leibler divergence under some constrains. It is shown that the derivatives of the Kullback-Leibler divergence for exact solutions and for approximate solutions are described by the same formula. In consequence if in a dynamical system the Kullback-Leibler divergence decreases in time for exact solutions, it also decreases for approximate solutions.

PL

W pracy przedstawiono algorytm, który umożliwia skonstruowanie przybliżonych rozwiązań dla pewnej klasy systemów dynamiczych opisujących ewolucję w czasie gęstości prawdopodobieństwa. Przybliżone rozwiązania otrzymujemy minimalizując informację Kullbacka-Leiblera przy dodatkowych warunkach. Wykazano, że pochodna informacji Kullbacka-Leiblera dla dokładnych i przybliżonych rozwiązań jest opisana przez tą samą formułę. W konsekwencji gdy w dynamicznym systemie maleje informacja Kullbacka-Leiblera dla dokładnych rozwiązań to także maleje dla przybliżonych rozwiązań.

9

Równoległy heurystyczny algorytm dla rozwiązywania problemu trasowania pojazdów z oknami czasowymi

Nalepa J., Czech Z.

Studia Informatica

|

2012

|

Vol. 33, nr 1

91-106

PL

W niniejszej pracy został przedstawiony równoległy heurystyczny algorytm dla rozwiązywania problemu trasowania pojazdów z oknami czasowymi. W pierwszej fazie jest minimalizowany rozmiar floty, a w drugiej fazie całkowita przebyta odległość. Celem pracy jest porównanie jakości rozwiązań otrzymanych za pomocą algorytmu sekwencyjnego oraz równoległego w pierwszej fazie. Przeanalizowany został wpływ zróżnicowania populacji i generowania rozwiązań potomnych na jakość rozwiązań wraz z przyspieszeniami dla algorytmu memetycznego drugiej fazy. Jakość rozwiązań jest oceniana na podstawie najlepszych obecnie znanych wyników dla problemów testowych Gehringa i Hombergera.

EN

The following article presents a parallel heuristic algorithm to solve the vehicle routing problem with time windows (VRPTW). The fleet size is minimized in the first phase and the traveled distance in the second one. The objective is to compare the accuracy of solutions obtained by the sequential and the parallel heuristics in the first phase. The influence of the population diversification and child generation on the accuracy is analyzed together with the speedups for the memetic algorithm in the second phase. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger’s benchmarking tests.

10

An improved route minimization algorithm for the vehicle routing problem with time Windows

Błocho M., Czech Z.

Studia Informatica

|

2011

|

Vol. 32, nr 3B

5-19

EN

A route minimization algorithm for the vehicle routing problem with time windows is presented. It was elaborated as an improvement of the algorithm proposed by Nagata and Bräysy (A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters 27, 2009, 333-338). By making use of the improved algorithm the two new-best solutions for Gehring and Homberger's (GH) benchmarks were found. The experiments showed that the algorithm constructs the world-best solutions with the minimum route numbers for the GH tests in a short time.

PL

W pracy zaprezentowano algorytm minimalizacji liczby tras dla problemu trasowania pojazdów z oknami czasowymi. Został on opracowany przez ulepszenie algorytmu zaproponowanego przez Nagatę and Bräysy'ego (A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters 27, 2009, 333-338). Przy użyciu ulepszonego algorytmu znaleziono dwa nowe najlepsze rozwiązania dla testów wzorcowych Gehringa i Hombergera (GH). W eksperymentach wykazano, że za pomocą ulepszonego algorytmu są konstruowane w krótkim czasie najlepsze światowe rozwiązania testów GH o minimalnej liczbie tras.

11

Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms

Tarapata Z.

International Journal of Applied Mathematics and Computer Science

|

2007

|

Vol. 17, no 2

269-287

EN

The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multiobjective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness of solving selected MOSP problems defined as mathematical programming problems (using the CPLEX 7.0 solver) and multi-weighted graph problems (using modified Dijkstra’s algorithm) is given. Experimental results of using the presented methods for multicriteria path selection in a terrain-based grid network are given.