Search
Search results for: greedy algorithm
-
An Approximation of the Zero Error Capacity by a Greedy Algorithm
PublicationWe 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
PublicationWe 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.
PublicationWe 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
PublicationWe 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
Publication -
On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn 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
PublicationIn 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
PublicationA 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
PublicationA 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
PublicationThe 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
PublicationFor 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
PublicationA 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
PublicationThis 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
PublicationPrzedstawiono 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
PublicationThe 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
PublicationThe 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
PublicationDepth 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
PublicationThis 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
PublicationThe 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
PublicationRozważ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...
-
Analysis-by-synthesis paradigm evolved into a new concept
PublicationThis work aims at showing how the well-known analysis-by-synthesis paradigm has recently been evolved into a new concept. However, in contrast to the original idea stating that the created sound should not fail to pass the foolproof synthesis test, the recent development is a consequence of the need to create new data. Deep learning models are greedy algorithms requiring a vast amount of data that, in addition, should be correctly...
-
5G Millimeter Wave Network Optimization: Dual Connectivity and Power Allocation Strategy
PublicationThe fifth generation (5G) of mobile networks utilizing millimeter Wave (mmWave) bands can be considered the leading player in meeting the continuously increasing hunger of the end user demands in the near future. However, 5G networks are characterized by high power consumption, which poses a significant challenge to the efficient management of base stations (BSs) and user association. Implementing new power consumption and user...
-
A multithreaded CUDA and OpenMP based power‐aware programming framework for multi‐node GPU systems
PublicationIn the paper, we have proposed a framework that allows programming a parallel application for a multi-node system, with one or more GPUs per node, using an OpenMP+extended CUDA API. OpenMP is used for launching threads responsible for management of particular GPUs and extended CUDA calls allow to manage CUDA objects, data and launch kernels. The framework hides inter-node MPI communication from the programmer who can benefit from...
-
GreedyMAX-type Algorithms for the Maximum Independent Set Problem
PublicationA maximum independent set problem for a simple graph G = (V,E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued functionp defined on the vertex set V(G) and called a potential function of agraph G, while P(G) = max{vinV(G)| p(v)} is called a potential of G. For any graph P(G) <= D(G),...
-
Dynamic coloring of graphs
PublicationDynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...
-
Minimum order of graphs with given coloring parameters
PublicationA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
ANYTIME POLYNOMIAL HEURISTIC ALGORITHM FOR PARTITIONING GROUPS OF DATA WITH PRESERVING CLASS PROPORTIONS FOR CROSS-VALIDATION
PublicationThe article describes a problem of splitting data for k-fold cross-validation, where class proportions must be preserved, with additional constraint that data is divided into groups that cannot be split into different cross-validation sets. This problem often occurs in e.g. medical data processing, where data samples from one patient must be included in the same cross-validation set. As this problem is NP-complete, a heuristic...