Wyniki wyszukiwania - BazTech

1

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.

2

Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification

Sydow M.

Mathematica Applicanda

|

2014

|

Vol. 42, No. 2

241--257

EN

Facility Dispersion Problem, originally studied in Operations Research, has recently found important new applications in Result Diversification approach in information sciences. This optimisation problem consists of selecting a small set of p items out of a large set of candidates to maximise a given objective function. The function expresses the notion of dispersion of a set of selected items in terms of a pair-wise distance measure between items. In most known formulations the problem is NP-hard, but there exist 2-approximation algorithms for some cases if distance satisfies triangle inequality. We present generalised 2/ approximation guarantees for the Facility Dispersion Problem in its two most common variants: Max Sum and Max Min, when the underlying dissimilarity measure satisfies parameterised triangle inequality with parameter α. The results apply to both relaxed and stronger variants of the triangle inequality. We also demonstrate potential applications of our findings in the result diversification problem including web search or entity summarisation in semantic knowledge graphs, as well as in practical computations on finite data sets.

PL

Problem „Facility Dispersion”, pierwotnie studiowany w badaniach operacyjnych, znajduje od niedawna nowe ważne zastosowania w podejściu polegającym na dywersyfikacji wyników w naukach informacyjnych. Jest to problem optymalizacji dyskretnej polegający na wyborze niewielkiego zbioru p elementów z pewnego dużego zbioru kandydatów tak, aby zmaksymalizować pewną funkcję celu. Funkcja ta wyraża „rozproszenie” wybranych elementów, za pośrednictwem pomocnicznej miary odległości par elementów. Problem jest NP-trudny w większości znanych wariantów, lecz istnieją algorytmy aproksymacyjne o współczynniku 2 dla niektórych z nich, gdy miara odległości jest metryką. W artykule zaprezentowano twierdzenia, które uogólniają znane wyniki do przypadku gdy miara odległości spełnia parametryzowaną nierówność trójkąta z parametrem alfa, dla wariantów „Max Sum” oraz „Max Min”problemu. Wyniki dotyczą zarówno osłabionej jak i wzmocnionej nierówności trójkąta. Zademonstrowano także potencjalne zastosowania powyższych rezultatów w problemie dywersyfikacji wyników w takich dziedzinach jak wyszukiwanie informacji czy podsumowania encyj w semantycznych grafach wiedzy, jak również w praktycznych obliczeniach na skończonych zbiorach danych.

3

Bin packing with restricted item fragmentation

Pieńkosz K.

Control and Cybernetics

|

2014

|

Vol. 43, no. 4

547--556

EN

In this paper we consider a generalization of the bin packing problem, in which it is permitted to fragment the items while packing them into bins. There is, however, a restriction that the size of each piece of the fragmented item cannot be smaller than a given parameter β An interesting aspect of such a model is that if β= 0, then the problem can be easily solved optimally. If β is large enough, meaning, in fact, that the fragmentation is not allowed, we get the classical bin packing problem, which is NP-hard in the strong sense. We present approximation algorithms for solving the problem and analyse their properties. The results of computational experiments and conclusions relating to the effectiveness of the algorithms are also presented.

4

A computational study of approximation algorithms for a minmax resource allocation problem

Przybysławski B., Kasperski A.

Operations Research and Decisions

|

2012

|

Vol. 22, No. 2

35--43

EN

A basic resource allocation problem with uncertain costs has been discussed. The problem is to minimize the total cost of choosing exactly p items out of n available. The uncertain item costs are specified as a discrete scenario set and the minmax criterion is used to choose a solution. This problem is known to be NP-hard, but several approximation algorithms exist. The aim of this paper is to investigate the quality of the solutions returned by these approximation algorithms. According to the results obtained, the randomized algorithms described are fast and output solutions of good quality, even if the problem size is large.

5

The database of interval orders difficult for the jump number minimizing algorithms

Krysztowiak P.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2011

|

Vol. 11, no. 1

15-22

EN

The problems of scheduling jobs on a single machine subject to precedence constraints can often be modelled as the jump number problem for posets, where a linear extension of a given partial order is to be found which minimizes the number of noncomparabilities. In this paper, we are investigating a restricted class of posets, called interval orders, admitting approximation algorithms for the jump number problem, in which the problem remains NP-complete. We have implemented three known approximation algorithms for this problem, all of which are guaranteed to produce solutions that are at most 50% worse than the optimal ones. More importantly, we have performed an exhaustive search for particularly hard interval orders, which enforce the algorithms to generate orderings which are exactly 50% worse than the optimal linear extensions. The main purpose of this paper is to present the database of those problematic posets.

6

Complexity of Searching for a Black Hole

Czyzowicz J., Kowalski D., Markou E., Pelc A.

Fundamenta Informaticae

|

2006

|

Vol. 71, nr 2,3

229-242

EN

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and given starting node we are interested in the fastest possible black hole search by two agents, under the general scenario in which some subset of nodes is safe and the black hole can be located in one of the remaining nodes. We show that the problem of finding the fastest possible black hole search scheme by two agents is NP-hard, and we give a 9.3-approximation for it.

7

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs

Karpinski M., Kowaluk M., Lingas A.

Fundamenta Informaticae

|

2004

|

Vol. 62, nr 3,4

369--375

EN

The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 ≤ k Ł≤8, by deriving some improved transformations from a maximum cut into a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively.

8

Maximizing the number of unused bins

Demange M., Monnot J., Paschos V. T.

Foundations of Computing and Decision Sciences

|

2001

|

Vol. 26, No. 2

169-186

EN

We analyze the approximation behavior of some of the best-known polynomial-time approximation algorithms for bin-packing under an approximation criterion, called differential ratio, informally the ratio (n — where n is the size of the input list, is the size of the solution provided by an approximation algorithm and Beta(I) is the size of the optimal one. This measure has originally been introduced by Ausiello, D'Atri and Protasi and more recently revisited, in a more systematic way, by the first and the third authors of the present paper. Under the differential ratio, bin-packing has a natural formulation as the problem of maximizing the number of unused bins. We first show that two basic fit bin-packing algorithms, the first-fit and the best-fit, admit differential approximation ratios 1/2. Next, we show that slightly improved versions of them achieve ratios 2/3. Refining our analysis we show that the famous first-fit-decreasing and best-fit decreasing algorithms achieve differential approximation ratio 3/4: Finally, we show that first-fit-decreasing achieves asymptotic differential approximation ratio 7/9.