Wyszukiwarka
Filtry
wszystkich: 66
Wyniki wyszukiwania dla: APPROXIMATION ALGORITHM
-
Proximal primal–dual best approximation algorithm with memory
PublikacjaWe propose a new modified primal–dual proximal best approximation method for solving convex not necessarily differentiable optimization problems. The novelty of the method relies on introducing memory by taking into account iterates computed in previous steps in the formulas defining current iterate. To this end we consider projections onto intersections of halfspaces generated on the basis of the current as well as the previous...
-
An Approximation Algorithm for Diagnostic Test Scheduling in Multicomputer Systems
Publikacja -
An approximation algorithm for maximum P3-packing in subcubic graphs
PublikacjaW pracy podano algorytm 4/3-przyliżony dla trudnego obliczeniowo problemu umieszczania wierzchołkowo rozłącznych dwukrawędziowych ścieżek w grafach o stopniu maksymalnym 3 i stopniu minimalnym 2. Poprawiono tym samym wcześniejsze wyniki dla grafów kubicznych (A. Kelmans, D. Mubayi, Journal of Graph Theory 45, 2004).
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublikacjaWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
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.
-
International Workshop on Approximation Algorithms for Combinatorial Optimization Problems
Konferencje -
Improved magnitude estimation of complex numbers using alpha max and beta min algorithm
PublikacjaThe paper presents an improved algorithm for calculating the magnitude of complex numbers. This problem, which is a special case of square rooting, occurs for example, in FFT processors and complex FIR filters. The proposed method of magnitude calculation makes use of the modified alpha max and beta min algorithm. The improved version of the algorithm allows to control the maximum magnitude approximation error by using an adequate...
-
FPGA realization of an improved alpha max plus beta min algorithm
PublikacjaThe generalized improved version of the alpha max plus beta min square-rooting algorithm and its realization in the Field Programmable Gate Array (FPGA) are presented. The algorithm computes the square root to calculate the approximate magnitude of a complex sample. It is especially useful for pipelined calculations in the DSP. In case of four approximation regions it is possible to reduce the peak error form 3.95% to 0.33%. This...
-
Pareto Ranking Bisection Algorithm for EM-Driven Multi-Objective Design of Antennas in Highly-Dimensional Parameter Spaces
PublikacjaA deterministic technique for fast surrogate-assisted multi-objective design optimization of antennas in highly-dimensional parameters spaces has been discussed. In this two-stage approach, the initial approximation of the Pareto set representing the best compromise between conflicting objectives is obtained using a bisection algorithm which finds new Pareto-optimal designs by dividing the line segments interconnecting previously...
-
Application of the Monte Carlo algorithm for solving volume integral equation in light scattering simulations
PublikacjaVarious numerical methods were proposed for analysis of the light scattering phenomenon. Important group of these methods is based on solving the volume integral equation describing the light scattering process. The popular method from this group is the discrete dipole approximation (DDA). DDA uses various numerical algorithms to solve the discretized integral equation. In the recent years, the application of the Monte Carlo (MC)...
-
Low-Cost Multi-Objective Optimization of Antennas By Means Of Generalized Pareto Ranking Bisection Algorithm
PublikacjaThis paper introduces a generalized Pareto ranking bisection algorithm for low-cost multi-objective design optimization of antenna structures. The algorithm allows for identifying a set of Pareto optimal sets of parameters (that represent the best trade-offs between considered objectives) by iterative partitioning of the intervals connecting previously found designs and executing a Pareto-ranking-based poll search. The initial...
-
Approximation of Fractional Order Dynamic Systems Using Elman, GRU and LSTM Neural Networks
PublikacjaIn the paper, authors explore the possibility of using the recurrent neural networks (RNN) - Elman, GRU and LSTM - for an approximation of the solution of the fractional-orders differential equations. The RNN network parameters are estimated via optimisation with the second order L-BFGS algorithm. It is done based on data from four systems: simple first and second fractional order LTI systems, a system of fractional-order point...
-
Shared processor scheduling
PublikacjaWe study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an (log)-time optimization algorithm for a class...
-
Locating and Identifying Ferromagnetic Objects
PublikacjaThe new non-iterative method of determining the dipole moment and location is presented in this paper. The algorithm of an object's localization and identification was achieved by using numerical calculations and approximation method. The arbitrary shapes of an object were assumed in the identification algorithm - axially symmetric spheroid (a prolate and an oblate). Several examples of localization and identification of an object's...
-
Locating and Identifying Ferromagnetic Objects
PublikacjaThe new non-iterative method of determining the dipole moment and location is presented in this paper. The algorithm of an object's localization and identification was achieved by using numerical calculations and approximation method. The arbitrary shapes of an object were assumed in the identification algorithm - axially symmetric spheroid (a prolate and an oblate). Several examples of localization and identification of an object's...
-
Cost-efficient multi-objective design optimization of antennas in highly-dimensional parameter spaces
PublikacjaMulti-objective optimization of antenna structures in highly-dimensional parameter spaces is investigated. For expedited design, variable-fidelity EM simulations and domain patching algorithm are utilized. The results obtained for a monopole antenna with 13 geometry parameters are compared with surrogate-assisted optimization involving response surface approximation modeling.
-
Impact of Low Switching-to-Fundamental Frequency Ratio on Predictive Current Control of PMSM: A simulation study
PublikacjaPredictive current control algorithms for permanent magnet synchronous (PMSM) drives rely on an assumption that within short intervals motor currents can be approximated with linear functions. This approximation may result either from discretizing the motor model or from simplifications applied to the continuous-time model. As the linear current approximation has been recognized as inaccurate in case when the drive operates with...
-
Solution of the dike-break problem using finite volume method and splitting technique
PublikacjaIn the paper the finite volume method (FVM) is presented for the solution of two-dimensional shallow water equations. These equations are frequently used to simulate the dam-break and dike-break induced flows. The applied numerical algorithm of FVM is based on the wave-propagation algorithm which ensures a stable solution and simultaneously minimizes the numerical errors. The dimensional decomposition according to the coordinate...
-
Algorithm for Automatic Wear Estimation of Railway Contact Strips Based on 3D Scanning Results
PublikacjaElectric rail vehicles use current collection system which consists of overhead contact line and a current collector (pantograph) mounted on the roof of a vehicle. A pantograph is equipped with contact strips, which slide along the contact wire, ensuring steady electric contact. Contact strips are made of carbon layer, fixed to an aluminum carrier. The carbon layer wears down due to friction. Using overly worn contact strips increases...
-
Rotational Design Space Reduction for Cost-Efficient Multi-Objective Antenna Optimization
PublikacjaCost-efficient multi-objective design of antenna structures is presented. Our approach is based on design space reduction algorithm using auxiliary single-objective optimization runs and coordinate system rotation. The initial set of Pareto-optimal solutions is obtained by optimizing a response surface approximation model established in the reduced space using coarse-discretization EM simulation data. The optimization engine is...
-
Shared processor scheduling of multiprocessor jobs
PublikacjaWe study a problem of shared processor scheduling of multiprocessor weighted jobs. Each job can be executed on its private processor and simultaneously on possibly many processors shared by all jobs. This simultaneous execution reduces their completion times due to the processing time overlap. Each of the m shared processors may charge a different fee but otherwise the processors are identical. The goal is to maximize the total...
-
Rozpoznawanie oraz lokalizacja w obrazie przewodów linii wysokiego napięcia
PublikacjaW pracy przedstawiono opracowany algorytm rozpoznawania oraz lokalizacji przewodów linii wysokiego napięcia na podstawie obrazu horyzontalnego. Procedura detekcji przewodu została podzielona na trzy etapy. Pierwszy etap zawiera algorytm wykrywania krawędzi wykazujący największą czułość na krawędzie poziome, a jednocześnie brak czułości na krawędzie pionowe. Efektem jest znaczna redukcja liczby wykrytych krawędzi w porównaniu do...
-
Grid Implementation of a Parallel Multiobjective Genetic Algorithm for Optimized Allocation of Chlorination Stations in Drinking Water Distribution Systems: Chojnice Case Study
PublikacjaSolving multiobjective optimization problems requires suitable algorithms to find a satisfactory approximation of a globally optimal Pareto front. Furthermore, it is a computationally demanding task. In this paper, the grid implementation of a distributed multiobjective genetic algorithm is presented. The distributed version of the algorithm is based on the island algorithm with forgetting island elitism used instead of a genetic...
-
Optimal shape design of multi-element trawl-doors using local surrogate models
PublikacjaTrawl-doors have a large influence on the fuel consumption of fishing vessels. Design and optimiza-tion of trawl-doors using computational models are a key factor in minimizing the fuel consump-tion. This paper presents an optimization algorithm for the shape design of trawl-door shapes using computational fluid dynamic (CFD) models. Accurate CFD models are computationally expensive. Therefore, the direct use of traditional optimization...
-
Local response surface approximations and variable-fidelity electromagnetic simulations for computationally efficient microwave design optimisation
PublikacjaIn this study, the authors propose a robust and computationally efficient algorithm for simulation-driven design optimisation of microwave structures. Our technique exploits variable-fidelity electromagnetic models of the structure under consideration. The low-fidelity model is optimised using its local response surface approximation surrogates. The high-fidelity model is refined by space mapping with polynomial interpolation of...
-
Efficient Multi-Fidelity Design Optimization of Microwave Filters Using Adjoint Sensitivity
PublikacjaA simple and robust algorithm for computationally efficient design optimiza-tion of microwave filters is presented. Our approach exploits a trust-region (TR)-based algorithm that utilizes linear approximation of the filter response obtained using adjoint sensitivity. The algorithm is sequentially executed on a family of electromagnetic (EM)-simulated models of different fidelities, starting from a coarse-discretization one, and...
-
Fast Multi-Objective Antenna Design Through Variable-Fidelity EM Simulations
PublikacjaA technique for fast multi-objective antenna optimization is introduced. A kriging interpolation surrogate constructed from sampled coarse-mesh EM simulations is utilized by multi-objective evolutionary algorithm (MOEA) to obtain the initial Pareto front approximation. The surrogate is defined in a subset of the original design space, determined by means of independently optimized individual objectives. Response correction techniques...
-
Graph security testing
PublikacjaSet S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs...
-
Design Space Reduction for Expedited Multi-Objective Design Optimization of Antennas in Highly-Dimensional Spaces
PublikacjaA surrogate-based technique for efficient multi-objective antenna optimization is discussed. Our approach exploits response surface approximation (RSA) model constructed from low-fidelity antenna model data (here, obtained through coarse-discretization electromagnetic simulations). The RSA model enables fast determination of the best available trade-offs between conflicting design goals. The cost of RSA model construction for multi-parameter...
-
Numerical Solution of the Two-Dimensional Richards Equation Using Alternate Splitting Methods for Dimensional Decomposition
PublikacjaResearch on seepage flow in the vadose zone has largely been driven by engineering and environmental problems affecting many fields of geotechnics, hydrology, and agricultural science. Mathematical modeling of the subsurface flow under unsaturated conditions is an essential part of water resource management and planning. In order to determine such subsurface flow, the two-dimensional (2D) Richards equation can be used. However,...
-
Generalized Pareto ranking bisection for computationally feasible multi-objective antenna optimization
PublikacjaMulti-objective optimization (MO) allows for obtaining comprehensive information about possible design trade-offs of a given antenna structure. Yet, executing MO using the most popular class of techniques, population-based metaheuristics, may be computationally prohibitive when full-wave EM analysis is utilized for antenna evaluation. In this work, a low-cost and fully deterministic MO methodology is introduced. The proposed generalized...
-
Design space reduction and variable-fidelity EM simulations for feasible Pareto optimization of antennas
PublikacjaA computationally efficient procedure for multi-objective optimization of antenna structures is presented. In our approach, a response surface approximation (RSA) model created from sampled coarse-discretization EM antenna simulations is utilized to yield an initial set of Pareto-optimal designs using a multi-objective evolutionary algorithm. The final Pareto front representation for the high-fidelity model is obtained using surrogate-based...
-
Locally Adaptive Cooperative Kalman Smoothing and Its Application to Identification of Nonstationary Stochastic Systems
PublikacjaOne of the central problems of the stochastic approximation theory is the proper adjustment of the smoothing algorithm to the unknown, and possibly time-varying, rate and mode of variation of the estimated signals/parameters. In this paper we propose a novel locally adaptive parallel estimation scheme which can be used to solve the problem of fixed-interval Kalman smoothing in the presence of model uncertainty. The proposed solution...
-
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublikacjaLet G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...
-
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
PublikacjaW pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania....
-
Analysis of circular polarization antenna design trade‐offs using low‐cost EM‐driven multiobjective optimization
PublikacjaCircular polarization (CP) antennas are vital components of modern communication systems. Their design involves handling several requirements such as low reflection and axial ratio (AR) within the frequency range of interest. Small size is an important criterion for antenna mobility which is normally achieved as a by‐product of performance‐oriented modifications of the structure topology. In this work, multiobjective optimization...
-
Efficient Multi-Objective Simulation-Driven Antenna Design Using Co-Kriging
PublikacjaA methodology for fast multi-objective antenna optimization is presented. Our approach is based on response surface approximation (RSA) modeling and variable-fidelity electromagnetic (EM) simulations. In the design process, a computationally cheap RSA surrogate model constructed from sampled coarse-discretization EM antenna simulations is optimized using a multi-objective evolutionary algorithm. The initially determined Pareto...
-
On minimum cost edge searching
PublikacjaWe consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...
-
Rapid multi-objective design optimisation of compact microwave couplers by means of physics-based surrogates
PublikacjaThe authors introduce a methodology for fast multi-objective design optimisation of miniaturised microwave couplers. The approach exploits the surrogate-based optimisation paradigm with an underlying low-fidelity model constructed from an equivalent circuit of the structure under consideration, corrected through implicit and frequency space mapping. A fast prediction tool obtained this way is subsequently optimised by a multi-objective...
-
Dynamical description of quantum computing: generic nonlocality of quantumnoise
PublikacjaWe develop a dynamical non-Markovian description of quantum computing in the weak-coupling limit, in the lowest-order approximation. We show that the long-range memory of the quantum reservoir (such as the 1/t4 one exhibited by electromagnetic vacuum) produces a strong interrelation between the structure of noise and the quantum algorithm, implying nonlocal attacks of noise. This shows that the implicit assumption of quantum error...
-
Low-Cost EM-Simulation-Driven Multi-Objective Optimization of Antennas
PublikacjaA surrogate-based method for efficient multi-objective antenna optimization is presented. Our technique exploits response surface approximation (RSA) model constructed from sampled low-fidelity antenna model (here, obtained through coarse-discretization EM simulation). The RSA model enables fast determination of the best available trade-offs between conflicting design goals. A low-cost RSA model construction is possible through...
-
Flow Process Models for Pipeline Diagnosis
PublikacjaThis chapter examines the problem of modeling and parameterization of the transmission pipeline flow process. First, the base model for discrete time is presented, which is a reference for other developed models. Then, the diagonal approximation (AMDA) method is proposed, in which the tridiagonal sub-matrices of the recombination matrix are approximated by their diagonal counterparts, which allows for a simple determination of...
-
Low-Cost Multi-Objective Optimization Yagi-Uda Antenna in Multi-Dimensional Parameter Space
PublikacjaA surrogate-based technique for fast multi-objective optimization of a multi-parameter planar Yagi-Uda antenna structure is presented. The proposed method utilizes response surface approximation (RSA) models constructed using training samples obtained from evaluation of the low-fidelity antenna model. Utilization of the RSA models allowsfor fast determination of the best possible trade-offs between conflicting objectives in multi-objective...
-
Fast multi-objective design optimization of microwave and antenna structures using data-driven surrogates and domain segmentation
PublikacjaPurpose Strategies and algorithms for expedited design optimization of microwave and antenna structures in multi-objective setup are investigated. Design/methodology/approach Formulation of the multi-objective design problem oriented towards execution of the population-based metaheuristic algorithm within the segmented search space is investigated. Described algorithmic framework exploit variable fidelity modeling, physics- and...
-
Multi-fidelity EM simulations and constrained surrogate modelling for low-cost multi-objective design optimisation of antennas
PublikacjaIn this study, a technique for low-cost multi-objective design optimisation of antenna structures has been proposed. The proposed approach is an enhancement of a recently reported surrogate-assisted technique exploiting variable-fidelity electromagnetic (EM) simulations and auxiliary kriging interpolation surrogate, the latter utilised to produce the initial approximation of the Pareto set. A bottleneck of the procedure for higher-dimensional...
-
Computationally Efficient Multi-Objective Optimization of and Experimental Validation of Yagi-Uda Antenna
PublikacjaIn this paper, computationally efficient multi-objective optimization of antenna structures is discussed. As a design case, we consider a multi-parameter planar Yagi-Uda antenna structure, featuring a driven element, three directors, and a feeding structure. Direct optimization of the high-fidelity electromagnetic (EM) antenna model is prohibitive in computational terms. Instead, our design methodology exploits response surface...
-
Analysis of Floodplain Inundation Using 2D Nonlinear Diffusive Wave Equation Solved with Splitting Technique
PublikacjaIn the paper a solution of two-dimensional (2D) nonlinear diffusive wave equation in a partially dry and wet domain is considered. The splitting technique which allows to reduce 2D problem into the sequence of one-dimensional (1D) problems is applied. The obtained 1D equations with regard to x and y are spatially discretized using the modified finite element method with the linear shape functions. The applied modification referring...
-
Accelerated multi-objective design optimization of antennas by surrogate modeling and domain segmentation
PublikacjaMulti-objective optimization yields indispensable information about the best possible design trade-offs of an antenna structure, yet it is challenging if full-wave electromagnetic (EM) analysis is utilized for performance evaluation. The latter is a necessity for majority of contemporary antennas as it is the only way of achieving acceptable modeling accuracy. In this paper, a procedure for accelerated multi-objective design of...
-
Domain segmentation for low-cost surrogate-assisted multi-objective design optimisation of antennas
PublikacjaAbstract: Information regarding the best possible design trade-offs of an antenna structure can be obtained through multiobjective optimisation (MO). Unfortunately, MO is extremely challenging if full-wave electromagnetic (EM) simulation models are used for performance evaluation. Yet, for the majority of contemporary antennas, EM analysis is the only tool that ensures reliability. This study introduces a procedure for accelerated...
-
Recent advances in rapid multiobjective optimization of expensive simulation models in microwave and antenna engineering by Pareto front exploration
PublikacjaPractical engineering design problems are inherently multiobjective, that is, require simultaneous control of several (and often conflicting) criteria. In many situations, genuine multiobjective optimization is required to acquire comprehensive information about the system of interest. The most popular solution techniques are populationbased metaheuristics, however, they are not practical for handling expensive electromagnetic...