Browsing by Subject "computational complexity"

Now showing 1 - 12 of 12

Access status: Open Access ,
A note on hardness of multiprocessor scheduling with scheduling solution space tree
(Wydawnictwa AGH, 2023) Dwibedy, Debasis; Mohanty, Rakesh
We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is $\cal {NP}$-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is $\cal {NP}$-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.
Access status: Restricted ,
Algorytmiczne aspekty problemu Frobeniusa
(Data obrony: 2010-10-27) Nowak, Sebastian
Wydział Matematyki Stosowanej
Access status: Restricted ,
Frequency assignment in mobile networks in terms of linear programming
(Data obrony: 2014-07-07) Wójcik, Piotr
Wydział Matematyki Stosowanej
Access status: Open Access ,
Gwarantowanie bezpieczeństwa w systemie z połączeniami awaryjnymi
(Wydawnictwa AGH, 2009) Wrona, Łukasz
We are considering security guaranteeing in systems with tree topology, augmented by additional backup links. A group of mobile autonomous agents needs to capture an invader, regardless of his strategy. In literature this problem is modeled as graph searching. We narrow the currently known search number estimation for cacti of degree 3 to two possible values for each number of branches with search number less than, or equal to $k$. We also classify type (**) branches, which have a hub or an avenue.
Access status: Open Access ,
Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych
(Wydawnictwa AGH, 2011) Ocetkiewicz, Krzysztof; Kubale, Marek
Niniejszy artykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. Model matematyczny, który tutaj zastosowano, to szeregowanie zadań uwarunkowanych czasowo. Przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. Pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie.
Access status: Open Access ,
Kryptosystemy oparte na problemach trudnych obliczeniowo z wyszczególnieniem problemu faktoryzacji liczb całkowitych
(2005) Kapcia, Piotr
Publikacja przedstawia analizę złożoności obliczeniowej problemów matematycznych, na których opiera się konstrukcja, a zarazem bezpieczeństwo kryptosystemów klucza publicznego. Jednocześnie, na podstawie aktualnej wiedzy z obliczeniowej teorii liczb oraz informacji o możliwościach nowoczesnej techniki obliczeniowej, przedyskutowana została skuteczność algorytmów wykorzystywanych do rozwiązywania tych problemów.
Access status: Restricted ,
Porównanie algorytmu sortowania asocjacyjnego ASSORT z innymi najefektywniejszymi algorytmami sortującymi
(Data obrony: 2017-01-18) Perlak, Michał
Wydział Elektrotechniki, Automatyki, Informatyki i Inżynierii Biomedycznej
Access status: Restricted ,
Porównanie skuteczności metod heurystycznych w problemach NP-trudnych
(Data obrony: 2018-10-15) Burek, Maciej
Wydział Elektrotechniki, Automatyki, Informatyki i Inżynierii Biomedycznej
Access status: Restricted ,
Problem najkrótszej ścieżki w sieciach dynamicznych
(Data obrony: 2017-10-30) Rzepecka, Kalina
Wydział Matematyki Stosowanej
Access status: Open Access ,
Scheduling jobs with linear model of simultaneous ageing and learning effects
(2011) Janiak, Adam; Lichtenstein, Maciej; Rusoń, Agata
In the paper, we introduce some new scheduling model in which learning and aging effects are both considered simultaneously. In this model the actual processing time of the jobs depends only on its position in a schedule and can be described by the piecewise linear function. For single-processor problem with introduced model, we show that the problem of minimizing the makespan criterion for independent jobs with release dates is strongly NP-hard, but some special cases of this problem are polynomially solvable. Based on those special cases, we propose 4 heuristic algorithms and we experimentally examine their usefulness for solving the general problem.
Access status: Restricted ,
The complexity of control problems in elections
(Data obrony: 2011-12-07) Wojtas, Krzysztof
Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki
Access status: Open Access ,
Very fast non-dominated sorting
(2014) Smutnicki, Czesław; Rudy, Jarosław; Żelazny, Dominik
A new and very efficient parallel algorithm for the Fast Non-dominated Sorting of Pareto fronts is proposed. By decreasing its computational complexity, the application of the proposed method allows us to increase the speedup of the best up to now Fast and Elitist Multi-Objective Genetic Algorithm (NSGA-II) more than two orders of magnitude. Formal proofs of time complexities of basic as well as improved versions of the procedure are presented. The provided experimental results fully confirm theoretical findings.