PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 11

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  algorytm aproksymacyjny
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available 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
Content available remote 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
Content available 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.
4
Content available 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.
5
Content available Zastosowanie aproksymacji wielomianowej do wyznaczania załomków EKG
Maciejewski M.
Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska
|
2017
|
T. 7, nr 4
92--95
PL
W celu wdrożenia elementów systemu telemedycznego związanego z diagnostyką [3], konieczne jest wcześniejsze zweryfikowanie wartości diagnostycznej algorytmów decyzyjnych odpowiedzialnych za wykrywanie stanów zagrożenia życia. Analiza przebiegu EKG jest w stanie dać informację o wielu takich stanach związanych z zaburzeniami układu krążenia [8]. W tym celu konieczne jest podjęcie szeregu działań prowadzących do budowy odpowiednich modeli. Pierwszym krokiem jest filtracja i przygotowanie danych [1], następnie ekstrakcja parametrów z przebiegów EKG, analiza wyników, porównanie ich z posiadanymi modelami oraz postawienie diagnozy. Każdy z tych kroków wymaga zastosowania odpowiedniego podejścia w celu zminimalizowania popełnianego błędu [4], wynikającego z niekiedy znacznie zniekształconego sygnału [7]. W celu ekstrakcji parametrów czasowych z odfiltrowanego i przygotowanego sygnału EKG konieczne jest najpierw wykrycie załomka R w zespole QRS [6], następnie wyznaczenie załomków P, Q, S, T i znalezienie ich początku i końca oraz określenie interesujących nas interwałów [2]. Zaproponowana tutaj metoda bazuje na aproksymacji przebiegu w oknie czasowym zawierającym dany załomek wielomianem określonego rzędu. Takie podejście pozwala następnie na wyznaczenie punktów przegięcia i, co za tym idzie, granic załomka. Metoda została zastosowana do przetwarzania przebiegów zarejestrowanych w warunkach laboratoryjnych w spoczynku i w trakcie kontrolowanego wysiłku, wyniki zostały porównane i przedstawione w niniejszej pracy.
EN
To succesfully implement a telemedical system for diagnostic purposes it is necessary to verify the diagnostic value of the decision algorithms used to detect life threatening situations. ECG analysis is a useful tool for obtaining information about the overall patient condition, especially for the circulatory system. Proper recognition cannot be performed without creation of proper models, The first step is signal filtration and data preparation, followed by parameter extraction, comparison with the model and diagnosis presentation. Each of these steps reqires a certain approach to minimize the error. Proper filtration needs to be performed. Then, the QRS complex is detected and rythm is calculated. Afterwards, the remaining waves are detected. To be able to perform valuable time dependencies it is necessary to exactly mark the beginnings and ends of intervals. The proposed method is based on opproximating the signal around the wave with a polynomial of a certain degree. This allows detection of inflection points corresponding to the borders of the wave. The method was applied to a set of ECG signals recorced during rest and activity, the results are presented and discussed.
6
Content available 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.
7
Content available 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ń.
8
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.
9
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.
10
Content available remote 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.
11
Problem szeregowania zadań wykonywanych na jednej maszynie z dynamicznym modelem terminów ich dostępności
Janiak A., Słoniński P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
167-177
PL
W niniejszej pracy zaprezentowano rozwiązanie problemu minimalizacji czasu zakończenia wykonywania zbioru n zadań o dynamicznych modelach terminów dostępności na pojedynczej maszynie krytycznej. Dane jest ograniczenie na ilość zasobu dostępną do rozdysponowania w danej chwili. Wykazano szereg istotnych własności tego problemu, a na ich podstawie skonstruowano algorytm optymalnego rozdziału zasobu dla zadań w ustalonej permutacji oraz algorytm aproksymacyjny szeregowania zadań.
EN
The aim of this contribution is to present the solution of the problem of minimizing the time of processing a set of n jobs with dynamical (differential) models of job release dates on a single critical machine. The amount of resource available at each moment is known a priori. Many important properties of this problem have been proven. They are the base for construction of optimal resource allocation algorithm for jobs processed in a given permutation. There is also presented the approximation algorithm for the scheduling problem.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.