Wyszukiwarka
Filtry
wszystkich: 27
Wyniki wyszukiwania dla: greedy algorithm
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm
PublikacjaWe present a greedy algorithm that determines a lower bound on the zero error capacity. The algorithm has many new advantages, e.g., it does not store a whole product graph in a computer memory and it uses the so-called distributions in all dimensions to get a better approximation of the zero error capacity. We also show an additional application of our algorithm.
-
Graphs hard-to-process for greedy algorithm MIN
PublikacjaWe compare results of selected algorithms that approximate the independence number in terms of the quality of constructed solutions. Furthermore, we establish smallest hard- to-process graphs for the greedy algorithm MIN.
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm.
PublikacjaWe present a greedy algorithm that determines a lower bound on the zero error capacity. The algorithm has many new advantages, e.g., it does not store a whole product graph in a computer memory and it uses the so-called distributions in all dimensions to get a better approximation of the zero error capacity. We also show an additional application of our algorithm.
-
On zero-error codes produced by greedy algorithms
PublikacjaWe present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms.
-
Greedy algorithms for backbone graph coloring in KOALA library
Publikacja -
On Computational Aspects of Greedy Partitioning of Graphs
PublikacjaIn this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...
-
Computational aspects of greedy partitioning of graphs
PublikacjaIn this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...
-
Reliable Greedy Multipoint Model-Order Reduction Techniques for Finite-Element Analysis
PublikacjaA new greedy multipoint model-order reduction algorithm for fast frequency-domain finite-element method simulations of electromagnetic problems is proposed. The location of the expansion points and the size of the projection basis are determined based on a rigorous error estimator. Compared to previous multipoint methods, the quality of the error estimator is significantly improved by ensuring the orthogonality of the projection...
-
New potential functions for greedy independence and coloring
PublikacjaA potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...
-
The Potential of Greed for Independence
PublikacjaThe well-known lower bound on the independence number of a graph due to Caro and Wei can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so-called potential functions p(G) : V(G) -> N_0 defined on the vertex set of a graph G for which suitably...
-
On-line P-coloring of graphs
PublikacjaFor a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...
-
Dynamic F-free Coloring of Graphs
PublikacjaA problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...
-
Greedy Multipoint Model-Order Reduction Technique for Fast Computation of Scattering Parameters of Electromagnetic Systems
PublikacjaThis paper attempts to develop a new automated multipoint model-order reduction (MOR) technique, based on matching moments of the system input–output function, which would be suited for fast and accurate computation of scattering parameters for electromagnetic (EM) systems over a wide frequency band. To this end, two questions are addressed. Firstly, the cost of the wideband reduced model generation is optimized by automating a...
-
Rzadka reprezentacja sygnału niestacjonarnego w technice oszczędnego próbkowania
PublikacjaPrzedstawiono zastosowanie techniki oszczędnego próbkowania do rekonstrukcji sygnału niestacjonarnego na podstawie skompresowanych próbek w dziedzinie czas-częstotliwość. Zastosowano nadmiarowy algorytm z różnymi słownikami aby znaleźć rzadką reprezentację sygnału. Wyniki symulacji potwierdzają, że zastosowanie oszczędnego próbkowania pozwala na rekonstrukcję sygnału niestacjonarnego z małej liczby losowo pobranych próbek, z niewielką...
-
JamesBot - an intelligent agent playing StarCraft II
PublikacjaThe most popular method for optimizing a certain strategy based on a reward is Reinforcement Learning (RL). Lately, a big challenge for this technique are computer games such as StarCraft II which is a real-time strategy game, created by Blizzard. The main idea of this game is to fight between agents and control objects on the battlefield in order to defeat the enemy. This work concerns creating an autonomous bot using reinforced...
-
Dataset Characteristics and Their Impact on Offline Policy Learning of Contextual Multi-Armed Bandits
PublikacjaThe Contextual Multi-Armed Bandits (CMAB) framework is pivotal for learning to make decisions. However, due to challenges in deploying online algorithms, there is a shift towards offline policy learning, which relies on pre-existing datasets. This study examines the relationship between the quality of these datasets and the performance of offline policy learning algorithms, specifically, Neural Greedy and NeuraLCB. Our results...
-
Brief Announcement: Energy Constrained Depth First Search
PublikacjaDepth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer B (e.g. due...
-
Weighted Clustering for Bees Detection on Video Images
PublikacjaThis work describes a bee detection system to monitor bee colony conditions. The detection process on video images has been divided into 3 stages: determining the regions of interest (ROI) for a given frame, scanning the frame in ROI areas using the DNN-CNN classifier, in order to obtain a confidence of bee occurrence in each window in any position and any scale, and form one detection window from a cloud of windows provided by...
-
A Model-Order Reduction Approach for Electromagnetic Problems With Nonaffine Frequency Dependence
PublikacjaThe aim of this paper is to present a novel model-order reduction (MOR) technique for the efcient frequency-domain nite-element method (FEM) simulation of microwave components. It is based on the standard reduced-basis method, but the subsequent expansion frequency points are selected following the so-called sparsied greedy strategy. This feature makes it especially useful to perform a fast-frequency sweep of problems that lead...
-
The maximum edge-disjoint paths problem in complete graphs
PublikacjaRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...