Wyniki wyszukiwania - Biblioteka Nauki

1

Greedy Algorithm for Construction of Partial Association Rules

100%

Moshkov M. J. , Piliszczuk M.

Fundamenta Informaticae

|

2009

|

tom Vol. 92, nr 3

259-277

EN

Partial association rules can be used for representation of knowledge, for inference in expert systems, for construction of classifiers, and for filling missing values of attributes. This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during the greedy algorithm work, and results of theoretical and experimental study of association rules for the most part of binary information systems.

2

A Minimum-Spanning-Tree-Inspired Algorithm for Channel Assignment in 802.11 Networks

100%

Dolińska I. , Jakubowski M. , Masiukiewicz A. , Rządkowski G. , Piórczyński K.

International Journal of Electronics and Telecommunications

|

2016

|

tom Vol. 62, No. 4

379--388

EN

Channel assignment in 2.4 GHz band of 802.11 standard is still important issue as a lot of 2.4 GHz devices are in use. This band offers only three non-overlapping channels, so in crowded environment users can suffer from high interference level. In this paper, a greedy algorithm inspired by the Prim’s algorithm for finding minimum spanning trees (MSTs) in undirected graphs is considered for channel assignment in this type of networks. The proposed solution tested for example network distributions achieves results close to the exhaustive approach and is, in many cases, several orders of magnitude faster.

3

A greedy algorithm for the DNA sequencing by hybridization with positive and negative errors and information about repetitions

100%

Kwarciak K. , Formanowicz P.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2011

|

tom Vol. 59, nr 1

111-115

EN

In this paper a greedy algorithm for some variants of the sequencing by hybridization method is presented. In the standard version of the method information about repetitions is not available. In the paper it is assumed that a partial information of this type is a part of the problem instance. Here two simple but realistic models of this information are taken into consideration. The first one assumes it is known if a given element of a spectrum appears in the target sequence once or more than once. The second model uses the knowledge is a given element of a spectrum occurs in the analyzed sequence once, twice or at least three times. The proposed greedy algorithm solves the variant of the problem with positive and negative errors. Results of a computational experiment are reported which, among others, confirm that the additional information leads to the improvement of the obtained solutions. They also show that the more precise model of information increases the quality of reconstructed sequences.

4

Prowadzenie połączeń przez kanał dla problemów MID-DCRP

100%

Chmiel K.

Studia z Automatyki i Informatyki

|

1998

|

tom T. 23

53-82

PL

W pracy rozważana jest podklasa problemów o maksymalnej gęstości międzykolumnowej (MID-DCRP) klasy problemów gęstych DCRP. Przebadana została struktura tej klasy z punktu widzenia charakterystyki rozwiązania (Is, II, Ip), gdzie Is oznacza liczbę ścieżek, a II i Ip liczbę odpowiednio, lewych i prawych kolumn dodatkowych. Na tej podstawie wskazany został wielomianowy algorytm, prowadzący do optymalnego rozwiązania przy dwustopniowym kryterium liczby ścieżek i liczby kolumn.

EN

In the paper the class of maximum intercolumn density dense channel routing problems (MID-DCRP) is considered. The structure of the class with respect to the solution characteristic (Is, II, Ip) is investigated, where Is denotes the number of tracks and II, Ip denote the number of left and right additional columns, respectively. Presented results indicate a polynomial time algorithm, leading to the optimal solution in terms of the two level criterion: number of tracks - number of columns.

5

Neonatal Mortality by Gestational Age and Birth Weight in Italy, 1998-2003: A Record Linkage Study

100%

Marini C. , Nuccitelli A.

Statistics in Transition new series

|

2011

|

tom 12

|

nr 1

207-222

EN

Neonatal mortality rates by gestational age and birth weight category are important indicators of maternal and child health and care quality. However, due to recent laws on administrative simplification and privacy, these specific rates have not been calculated in Italy since 1999. The main aim of this work is to assess the possibility of retrieving information on neonatal mortality by the linkage between records related to live births and records related to infant deaths within the first month of life, with reference to 2003 and 2004 birth cohorts. From a strict methodological point of view, some critical aspects of the most used record linkage approach are highlighted: specific problems may arise from the choice of records to be linked if there are consistency constraints between pairs (in this context, one death record can be linked to at most one birth record). In the light of considerations on the quality of the starting data, the retrieval of information on neonatal mortality by gestational age and birth weight is restricted to Northern Italy. Specific neonatal mortality rates are provided with reference to 2003 and discussed with particular emphasis on quality issues in the data collection processes.

6

Greedy Algorithm with Weights for Decision Tree Construction

100%

Moshkov M. J.

Fundamenta Informaticae

|

2010

|

tom Vol. 104, nr 3

285-292

EN

An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.

7

Greedy Algorithm for Attribute Reduction

100%

Zielosko B. , Piliszczuk M.

Fundamenta Informaticae

|

2008

|

tom Vol. 85, nr 1-4

549-561

EN

In the paper the accuracy of greedy algorithm for construction of partial tests (superreducts) and partial decision rules is considered. Results of experiments with greedy algorithm are described.

8

A Greedy Algorithm for Construction of Decision Trees for Tables with Many-Valued Decisions : A Comparative Study

100%

Azad M. , Chikalov I. , Moshkov M. , Zielosko B.

Fundamenta Informaticae

|

2013

|

tom Vol. 128, nr 1-2

1--15

EN

In the paper, we study a greedy algorithm for construction of decision trees. This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. Experimental results for data sets from UCI Machine Learning Repository and randomly generated tables are presented. We make a comparative study of the depth and average depth of the constructed decision trees for proposed approach and approach based on generalized decision. The obtained results show that the proposed approach can be useful from the point of view of knowledge representation and algorithm construction.

9

Approximate algorithm for β -decision rule optimization

100%

Zielosko B. , Moshkov M.

Studia Informatica

|

2011

|

tom Vol. 32, nr 2A

329-335

EN

In the paper greedy algorithm for construction of β decision rules and algorithm for construction of β -complete systems of decision rules are studied. Obtined bounds on accuracy of the considered algorithms are presented.

PL

W artykule został przedstawiony algorytm zachłanny dla konstruowania β -reguł decyzyjnych oraz dla konstruowania β -kompletnych systemów reguł decyzyjnych. Zostały zaprezentowane granice dokładności wyników uzyskiwanych za pomocą rozważanych algorytmów.

10

Optimization of deployment of goods supply in a high storage warehouse by means of the greedy algorithm

100%

Sabo A.

Mathematical Economics

|

2012

|

nr 8 (15)

111-121

EN

A warehouse is one of the key areas in logistics. A large group of logistic problems is associated with the storage process. The optimization of logistic processes undoubtedly brings many benefits for businesses, both financial and organizational. This paper presents one of the most common problems which occurs in a specific type of warehouse – high storage warehouse. The problem is the location of the supply of goods in a high storage warehouse. Due to the large computational complexity of the problem, the paper proposes to use heuristic algorithms to solve the problem. The high storage warehouse is also a system that allows the comprehensive management of logistics operations in the warehouse by using information from a database and the corresponding data processing algorithms. The presented approach assumes the implementation of heuristic algorithms in the logistic warehouse management system and uses them in the high storage warehouse. This will allow the material management in the warehouse to become easier, faster and the decision-making to become more accurate.

11

Meta-heuristic approach based on genetic and greedy algorithms to solve flexible job-shop scheduling problem

88%

Rezaeipanah A. , Sarhangnia F. , Abdollahi M. J.

Computer Science

|

2021

|

tom T. 22 (4)

463--488

EN

Job-shop scheduling systems are one of the applications of group technology in industry, the purpose of which is to take advantage of the physical or operational similarities of products in their various aspects of construction and design. Additionally, these systems are identified as cellular manufacturing systems (CMS). In this paper, a meta-heuristic method that is based on combining genetic and greedy algorithms has been used in order to optimize and evaluate the performance criteria of the flexible job-shop scheduling problem. In order to improve the efficiency of the genetic algorithm, the initial population is generated by the greedy algorithm, and several elitist operators are used to improve the solutions. The greedy algorithm that is used to improve the generation of the initial population prioritizes the cells and the job in each cell and, thus, offers quality solutions. The proposed algorithm is tested over the P-FJSP dataset and compared with the state-of-the-art techniques of this literature. To evaluate the performance of the diversity, spacing, quality, and run-time criteria were used in a multi-objective function. The results of the simulation indicate the better performance of the proposed method as compared to the NRGA and NSGA-II methods.

12

Canonical greedy algorithms and dynamic programming

88%

Lew A.

Control and Cybernetics

|

2006

|

tom Vol. 35, no 3

621-643

EN

There has been little work on how to construct greedy algorithms to solve new optimization problems efficiently. Instead, greedy algorithms have generally been designed on an ad hoc basis. On the other hand, dynamic programming has a long history of being a useful tool for solving optimization problems, but is often inefficient. We show how dynamic programming can be used to derive efficient greedy algorithms that are optimal for a wide variety of problems. This approach also provides a way to obtain less efficient but optimal solutions to problems where derived greedy algorithms are nonoptimal.

13

Greedy Algorithms for Construction of Approximate Tests for Decision Tables with Many-Valued Decisions

88%

Azad M. , Chikalov I. , Moshkov M. , Zielosko B.

Fundamenta Informaticae

|

2012

|

tom Vol. 120, nr 3/4

231-242

EN

The paper is devoted to the study of a greedy algorithm for construction of approximate tests (super-reducts). This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. We consider bounds on the precision of this algorithm relative to the cardinality of tests.

14

A Reactive Search-Based Algorithm for Scheduling Multiprocessor Tasks on Two Dedicated Processors

75%

Aïder M. , Baatout F. Z. , Hifi M.

Annals of Computer Science and Information Systems

|

2020

|

tom Vol. 21

257--261

EN

In this paper, we propose a reactive search-based algorithm for solving the problem of scheduling multiprocessor tasks on two dedicated processors. An instance of the problem is characterized by a set of tasks divided into three subsets and two processors, where some tasks can be executed either on one processor or two processors. The goal of the problem is to determine the scheduling of all tasks minimizing the execution of the last assigned task. The proposed reactive search starts with a starting greedy solution. Next, a series of local operators combined with a tabu list are introduced in order to intensify the search process. The method is also reinforced with a drop and rebuild operator that is applied for diversifying the search process. Finally, the performance of the proposed method is evaluated on a set of benchmark instances, where its provided results are compared to those achieved by a recent method available in the literature. Encouraging results have been reached.

15

Algorytm zachłanny dla konstruowania częściowych reguł asocjacyjnych

75%

Zielosko B.

Studia Informatica

|

2010

|

tom Vol. 31, nr 2A

225-236

PL

W artykule przedstawiono sposób konstruowania częściowych reguł asocjacyjnych z wykorzystaniem algorytmu zachłannego. Podejście to jest odmienne od znanego algorytmu A priori i jego modyfikacji, wykorzystujących zbiory częste. Przedstawione wyniki badań oraz rezultaty z przeprowadzonych eksperymentów pokazują, że algorytm zachłanny pozwala konstruować stosunkowo małą liczbę krótkich, częściowych reguł asocjacyjnych o dobrej jakości, które pokrywają wszystkie obiekty danego systemu informacyjnego.

EN

The paper presents greedy algorithm for partial association rule construction. This approach is different from the known algorithm Apriori and its modifications based on frequent itemsets. Theoretical and experimental results show, that the greedy algorithm constructs relatively small number of short partial association rules which have good accuracy and cover all objects from given information system.

16

Approximation of Reset Thresholds with Greedy Algorithms

75%

Ananichev D. S. , Gusev V. V.

Fundamenta Informaticae

|

2016

|

tom 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.

17

Optymalizacja częściowych reguł asocjacyjnych względem liczby pomyłek

63%

Zielosko B. , Robaszkiewicz M.

Studia Informatica

|

2016

|

tom Vol. 37, nr 1

187--198

PL

Artykuł przedstawia optymalizację częściowych reguł asocjacyjnych generowanych przez algorytm zachłanny względem liczby pomyłek (błędnych zaklasyfikowań). Zaproponowana optymalizacja ma na celu: (i) uzyskanie reguł o stosunkowo dobrej jakości, które w kolejnych etapach badań zostaną wykorzystane do budowy klasyfikatorów, (ii) zmniejszenie liczby konstruowanych reguł, co ma znaczenie z punktu widzenia reprezentacji wiedzy. Praca przedstawia wyniki eksperymentalne dla zbiorów danych umieszczonych w Repozytorium Uczenia Maszynowego.

EN

In the paper, an optimization of partial association rules relative to number of misclassifications is presented. The aims of proposed optimization are: (i) construction of rules with small number of misclassifications, what is important from the point of view of construction of classifiers, (ii) decreasing the number of rules, what is important from the point of view of knowledge representation. The paper contains experimental results for data sets from UCI Machine Learning Repository.

18

Dijkstra's algorithm revisited: the dynamic programming connexion

63%

Sniedovich M.

Control and Cybernetics

|

2006

|

tom Vol. 35, no 3

599-620

EN

Dijkstra's Algorithm is one of the most popular algorithms in computer science. It is also popular in operations research. It is generally viewed and presented as a greedy algorithm. In this paper we attempt to change this perception by providing a dynamic programming perspective on the algorithm. In particular, we are reminded that this famous algorithm is strongly inspired by Bellman's Principle of Optimality and that both conceptually and technically it constitutes a dynamic programming successive approximation procedure par excellence. One of the immediate implications of this perspective is that this popular algorithm can be incorporated in the dynamic programming syllabus and in turn dynamic programming should be (at least) alluded to in a proper exposition/teaching of the algorithm.

19

Evolutionary and greedy exploration of the space of decision trees

63%

Biedrzycki R. , Arabas J.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

tom z. 156

61-68

EN

This paper addresses the issue of the decision trees induction. We define the space of all possible trees and try to find good trees by searching that space. We compare performance of an evolutionary algorithm and standard, problem-specific algorithms (ID3, C4.5).

20

Sieci kognitywne MANET

51%

Gajewski P. , Łopatka J. , Suchański M.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2014

|

tom nr 6

132--137

PL

Dokonano przeglądu zagadnień związanych z tworzeniem kognitywnych, mobilnych sieci doraźnych - MANET CR. Opisano dotychczasowe wyniki realizacji projektów związanych z opracowaniem i standaryzacją sieci radia kognitywnego - CR. Scharakteryzowano wybrane kognitywne rozwiązania dla mobilnych sieci doraźnych, głównie na podstawie wyników projektu CORASMA (Cognitive Radio for Spectrum Management) Europejskiej Agencji Obrony - EDA. Opisano przykład zastosowania algorytmu zachłannego dla rozproszonego zarządzania widmem w wojskowej sieci z grupowaniem węzłów. W zakończeniu omówiono drogę do uzyskania kognitywnej sieci radiowej dla potrzeb obronności kraju.

EN

In this paper a survey of the cognitive radio (CR) techniques for Mobile Ad Hoc Networks (MANET CR) is presented. The main results of up to now projects concerning development and standardization CR networks are described. The chosen solutions for MANET CR are also characterized. Here we mainly discuss the results of EDA project CORASMA, in which the greedy algorithm for frequency distributed management have been proposed for clustered MANET CR. The way to CR networks for national security is shown in the context of national and international activities in this area.