Branch-and-cut algorithms for the split delivery vehicle routing problem

NARCIS (Netherlands)

Archetti, Claudia; Bianchessi, Nicola; Speranza, M. Grazia

2014-01-01

In this paper we present two exact branch-and-cut algorithms for the Split Delivery Vehicle Routing Problem (SDVRP) based on two relaxed formulations that provide lower bounds to the optimum. Procedures to obtain feasible solutions to the SDVRP from a feasible solution to the relaxed formulations

A simple but usually fast branch-and-bound algorithm for the capacitated facility location problem

DEFF Research Database (Denmark)

Görtz, Simon; Klose, Andreas

2012-01-01

This paper presents a simple branch-and-bound method based on Lagrangean relaxation and subgradient optimization for solving large instances of the capacitated facility location problem (CFLP) to optimality. To guess a primal solution to the Lagrangean dual, we average solutions to the Lagrangean...... subproblem. Branching decisions are then based on this estimated (fractional) primal solution. Extensive numerical results reveal that the method is much faster and more robust than other state-of-the-art methods for solving the CFLP exactly....

A branch-and-price algorithm for the capacitated facility location problem

DEFF Research Database (Denmark)

Klose, Andreas; Görtz, Simon

2007-01-01

to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master...... problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances....

A branch-and-bound algorithm for the capacitated facility location problem with convex production costs

DEFF Research Database (Denmark)

Klose, Andreas

solution approaches: The use of perspective cuts, a second-order cone (SOC) MIP formulation for the case of quadratic costs, and Benders’ decomposition. Our computational results indicate that in many case the branch-and-bound method is superior to both the perspective cut approach, the SOC MIP...

A Branch and Bound Approach for Truss Topology Design Problems with Valid Inequalities

International Nuclear Information System (INIS)

Cerveira, Adelaide; Agra, Agostinho; Bastos, Fernando; Varum, Humberto

2010-01-01

One of the classical problems in the structural optimization field is the Truss Topology Design Problem (TTDP) which deals with the selection of optimal configuration for structural systems for applications in mechanical, civil, aerospace engineering, among others. In this paper we consider a TTDP where the goal is to find the stiffest truss, under a given load and with a bound on the total volume. The design variables are the cross-section areas of the truss bars that must be chosen from a given finite set. This results in a large-scale non-convex problem with discrete variables. This problem can be formulated as a Semidefinite Programming Problem (SDP problem) with binary variables. We propose a branch and bound algorithm to solve this problem. In this paper it is considered a binary formulation of the problem, to take advantage of its structure, which admits a Knapsack problem as subproblem. Thus, trying to improve the performance of the Branch and Bound, at each step, some valid inequalities for the Knapsack problem are included.

Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms

DEFF Research Database (Denmark)

Brodal, Gerth Stølting; Moruz, Gabriel

2005-01-01

Branch mispredictions is an important factor affecting the running time in practice. In this paper we consider tradeoffs between the number of branch mispredictions and the number of comparisons for sorting algorithms in the comparison model. We prove that a sorting algorithm using O(dnlog n......) comparisons performs Omega(nlogd n) branch mispredictions. We show that Multiway MergeSort achieves this tradeoff by adopting a multiway merger with a low number of branch mispredictions. For adaptive sorting algorithms we similarly obtain that an algorithm performing O(dn(1+log (1+Inv/n))) comparisons must...... perform Omega(nlogd (1+Inv/n)) branch mispredictions, where Inv is the number of inversions in the input. This tradeoff can be achieved by GenericSort by Estivill-Castro and Wood by adopting a multiway division protocol and a multiway merging algorithm with a low number of branch mispredictions....

A branch-and-cut algorithm for the vehicle routing problem with multiple use of vehicles

Directory of Open Access Journals (Sweden)

İsmail Karaoğlan

2015-06-01

Full Text Available This paper addresses the vehicle routing problem with multiple use of vehicles (VRPMUV, an important variant of the classic vehicle routing problem (VRP. Unlike the classical VRP, vehicles are allowed to use more than one route in the VRPMUV. We propose a branch-and-cut algorithm for solving the VRPMUV. The proposed algorithm includes several valid inequalities from the literature for the purpose of improving its lower bounds, and a heuristic algorithm based on simulated annealing and a mixed integer programming-based intensification procedure for obtaining the upper bounds. The algorithm is evaluated in terms of the test problems derived from the literature. The computational results which follow show that, if there were 120 customers on the route (in the simulation, the problem would be solved optimally in a reasonable amount of time.

Subdivision, Sampling, and Initialization Strategies for Simplical Branch and Bound in Global Optimization

DEFF Research Database (Denmark)

Clausen, Jens; Zilinskas, A,

2002-01-01

We consider the problem of optimizing a Lipshitzian function. The branch and bound technique is a well-known solution method, and the key components for this are the subdivision scheme, the bound calculation scheme, and the initialization. For Lipschitzian optimization, the bound calculations are...

A Mathematical Study on “Additive Technique” Versus “Branch and Bound Technique” for Solving Binary Programming Problem

Science.gov (United States)

Sufahani, Suliadi; Ghazali Kamardan, M.; Saifullah Rusiman, Mohd; Mohamad, Mahathir; Khalid, Kamil; Ali, Maselan; Khalid, Kamal; Nawawi, MKM; Ahmad, Asmala

2018-04-01

A solid body needs adequate supplements from nourishment that we eat each day. Eating pretty much than what our body needs will prompt lack of healthy sustenance (under-nourishment and over-nourishment). In Malaysia, a few reviews have been directed to examine the wholesome status of Malaysians, particularly among youngsters and youths. However there are different methods for taking care of the menu arranging issue and in this paper Binary Programming (BP) is executed. Separately, “Additive Technique (AT)” and “Branch and Bound Technique (BBT)” are utilized as a part of BP. Both methodologies utilize diverse systems and might yield distinctive ideal arrangements. Along these lines, this study expects to build up a scientific model for eating regimen arranging that meets the essential supplement admission and look at the outcomes yield through additive substance and branch and bound methodologies. The information was gathered from different all inclusive schools and furthermore from the Ministry of Education. The model was illuminated by utilizing the Balas Algorithm through AT and Binary Programming through BBT.

Automatic bounding estimation in modified NLMS algorithm

International Nuclear Information System (INIS)

Shahtalebi, K.; Doost-Hoseini, A.M.

2002-01-01

Modified Normalized Least Mean Square algorithm, which is a sign form of Nlm based on set-membership (S M) theory in the class of optimal bounding ellipsoid (OBE) algorithms, requires a priori knowledge of error bounds that is unknown in most applications. In a special but popular case of measurement noise, a simple algorithm has been proposed. With some simulation examples the performance of algorithm is compared with Modified Normalized Least Mean Square

A Partitioning and Bounded Variable Algorithm for Linear Programming

Science.gov (United States)

Sheskin, Theodore J.

2006-01-01

An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does…

Optimization method to branch-and-bound large SBO state spaces under dynamic probabilistic risk assessment via use of LENDIT scales and S2R2 sets

International Nuclear Information System (INIS)

Nielsen, Joseph; Tokuhiro, Akira; Khatry, Jivan; Hiromoto, Robert

2014-01-01

Traditional probabilistic risk assessment (PRA) methods have been developed to evaluate risk associated with complex systems; however, PRA methods lack the capability to evaluate complex dynamic systems. In these systems, time and energy scales associated with transient events may vary as a function of transition times and energies to arrive at a different physical state. Dynamic PRA (DPRA) methods provide a more rigorous analysis of complex dynamic systems. Unfortunately DPRA methods introduce issues associated with combinatorial explosion of states. In order to address this combinatorial complexity, a branch-and-bound optimization technique is applied to the DPRA formalism to control the combinatorial state explosion. In addition, a new characteristic scaling metric (LENDIT – length, energy, number, distribution, information and time) is proposed as linear constraints that are used to guide the branch-and-bound algorithm to limit the number of possible states to be analyzed. The LENDIT characterization is divided into four groups or sets – 'state, system, resource and response' (S2R2) – describing reactor operations (normal and off-normal). In this paper we introduce the branch-and-bound DPRA approach and the application of LENDIT scales and S2R2 sets to a station blackout (SBO) transient. (author)

Design of planar articulated mechanisms using branch and bound

DEFF Research Database (Denmark)

Stolpe, Mathias; Kawamoto, Atsushi

2004-01-01

This paper considers an optimization model and a solution method for the design of two-dimensional mechanical mechanisms. The mechanism design problem is modeled as a nonconvex mixed integer program which allows the optimal topology and geometry of the mechanism to be determined simultaneously...... and that buckling is prevented. The feasible set of the design problem is described by nonlinear differentiable and non-differentiable constraints as well as nonlinear matrix inequalities. To solve the mechanism design problem a branch and bound method based on convex relaxations is developed. To guarantee...... mechanism design problems of realistic size to global optimality....

Aplikasi Algoritma Branch and Bound Untuk Optimasi Jalur Pemadam Kebakaran Kota Yogyakarta

Directory of Open Access Journals (Sweden)

Sri Margiyani

2014-04-01

Full Text Available Kasus kebakaran di Indonesia, khususnya Kota Yogyakarta dari tahun ke tahun masih menunjukkan angka yang tinggi. Hal ini mengakibatkan kerugian yang cukup tinggi bagi korban kebakaran. Untuk meminimalisasi terjadinya korban jiwa dan kerugian secara material saat terjadi kebakaran, maka pihak pemadam kebakaran mengupayakan melalui rute terpendek untuk sampai di lokasi kebakaran. Tujuan dari penelitian ini adalah pencarian rute terpendek jalur pemadam kebakaran dari kantor pemadam sampai ke lokasi kebakaran. Permasalahan pencarian rute terpendek jalur pemadam kebakaran secara abstrak dapat digambarkan dengan suatu graf yang merupakan masalah optimasi dalam pencarian rute terpendek (Shortest Path Problem. Pemecahan permasalahan tersebut adalah dengan merepresentasikan peta pemadam kebakaran ke dalam bentuk graf berbobot dan berarah, selanjutnya permasalahan diselesaikan menggunakan Algoritma Branch and Bound. Perhitungan dilakukan secara manual dengan jarak (dalam meter sebagai bobot perhitungan.  Berdasarkan perhitungan menggunakan Algoritma Branch and Bound untuk optimasi jalur pemadam kebakaran Kota Yogyakarta untuk wilayah Kecamatan Umbulharjo menghasilkan solusi rute: Kantor pemadam kebakaran – Jln. Ipda Tut Harsono - Jln. Kusumanegara – Jln. Glagahsari – Kantor Kecamatan Umbulharjo dengan total jarak 5305 meter atau 5,035 km.

Spanning Trees whose Stems have a Bounded Number of Branch Vertices

Directory of Open Access Journals (Sweden)

Yan Zheng

2016-08-01

Full Text Available Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T. The subtree T − Leaf(T of T is called the stem of T and denoted by Stem(T. In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose stem has a bounded number of branch vertices, and these conditions are best possible.

Rational hybrid Monte Carlo algorithm for theories with unknown spectral bounds

International Nuclear Information System (INIS)

Kogut, J. B.; Sinclair, D. K.

2006-01-01

The Rational Hybrid Monte Carlo (RHMC) algorithm extends the Hybrid Monte Carlo algorithm for lattice QCD simulations to situations involving fractional powers of the determinant of the quadratic Dirac operator. This avoids the updating increment (dt) dependence of observables which plagues the Hybrid Molecular-dynamics (HMD) method. The RHMC algorithm uses rational approximations to fractional powers of the quadratic Dirac operator. Such approximations are only available when positive upper and lower bounds to the operator's spectrum are known. We apply the RHMC algorithm to simulations of 2 theories for which a positive lower spectral bound is unknown: lattice QCD with staggered quarks at finite isospin chemical potential and lattice QCD with massless staggered quarks and chiral 4-fermion interactions (χQCD). A choice of lower bound is made in each case, and the properties of the RHMC simulations these define are studied. Justification of our choices of lower bounds is made by comparing measurements with those from HMD simulations, and by comparing different choices of lower bounds

Algorithms for Protein Structure Prediction

DEFF Research Database (Denmark)

Paluszewski, Martin

-trace. Here we present three different approaches for reconstruction of C-traces from predictable measures. In our first approach [63, 62], the C-trace is positioned on a lattice and a tabu-search algorithm is applied to find minimum energy structures. The energy function is based on half-sphere-exposure (HSE......) is more robust than standard Monte Carlo search. In the second approach for reconstruction of C-traces, an exact branch and bound algorithm has been developed [67, 65]. The model is discrete and makes use of secondary structure predictions, HSE, CN and radius of gyration. We show how to compute good lower...... bounds for partial structures very fast. Using these lower bounds, we are able to find global minimum structures in a huge conformational space in reasonable time. We show that many of these global minimum structures are of good quality compared to the native structure. Our branch and bound algorithm...

Branch-pipe-routing approach for ships using improved genetic algorithm

Science.gov (United States)

Sui, Haiteng; Niu, Wentie

2016-09-01

Branch-pipe routing plays fundamental and critical roles in ship-pipe design. The branch-pipe-routing problem is a complex combinatorial optimization problem and is thus difficult to solve when depending only on human experts. A modified genetic-algorithm-based approach is proposed in this paper to solve this problem. The simplified layout space is first divided into threedimensional (3D) grids to build its mathematical model. Branch pipes in layout space are regarded as a combination of several two-point pipes, and the pipe route between two connection points is generated using an improved maze algorithm. The coding of branch pipes is then defined, and the genetic operators are devised, especially the complete crossover strategy that greatly accelerates the convergence speed. Finally, simulation tests demonstrate the performance of proposed method.

Disjunctive cuts in a branch-and-price algorithm for the capacitated vehicle routing problem

DEFF Research Database (Denmark)

Røpke, Stefan

This talk presents computational results that show the usefulness of the general-purpose valid inequalities disjunctive cuts when applied to the CVRP. Results indicate that the disjunctive cuts are able to reduce the gap between lower bound and upper bound more than state-of-the-art problem...... specific inequalities. Results also indicate that introducing the cuts leads to a smaller branch and bound tree and faster solution times overall....

Algorithm-Dependent Generalization Bounds for Multi-Task Learning.

Science.gov (United States)

Liu, Tongliang; Tao, Dacheng; Song, Mingli; Maybank, Stephen J

2017-02-01

Often, tasks are collected for multi-task learning (MTL) because they share similar feature structures. Based on this observation, in this paper, we present novel algorithm-dependent generalization bounds for MTL by exploiting the notion of algorithmic stability. We focus on the performance of one particular task and the average performance over multiple tasks by analyzing the generalization ability of a common parameter that is shared in MTL. When focusing on one particular task, with the help of a mild assumption on the feature structures, we interpret the function of the other tasks as a regularizer that produces a specific inductive bias. The algorithm for learning the common parameter, as well as the predictor, is thereby uniformly stable with respect to the domain of the particular task and has a generalization bound with a fast convergence rate of order O(1/n), where n is the sample size of the particular task. When focusing on the average performance over multiple tasks, we prove that a similar inductive bias exists under certain conditions on the feature structures. Thus, the corresponding algorithm for learning the common parameter is also uniformly stable with respect to the domains of the multiple tasks, and its generalization bound is of the order O(1/T), where T is the number of tasks. These theoretical analyses naturally show that the similarity of feature structures in MTL will lead to specific regularizations for predicting, which enables the learning algorithms to generalize fast and correctly from a few examples.

BPP: a sequence-based algorithm for branch point prediction.

Science.gov (United States)

Zhang, Qing; Fan, Xiaodan; Wang, Yejun; Sun, Ming-An; Shao, Jianlin; Guo, Dianjing

2017-10-15

Although high-throughput sequencing methods have been proposed to identify splicing branch points in the human genome, these methods can only detect a small fraction of the branch points subject to the sequencing depth, experimental cost and the expression level of the mRNA. An accurate computational model for branch point prediction is therefore an ongoing objective in human genome research. We here propose a novel branch point prediction algorithm that utilizes information on the branch point sequence and the polypyrimidine tract. Using experimentally validated data, we demonstrate that our proposed method outperforms existing methods. Availability and implementation: https://github.com/zhqingit/BPP. djguo@cuhk.edu.hk. Supplementary data are available at Bioinformatics online. © The Author (2017). Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oup.com

Optimal chiller sequencing by branch and bound method for saving energy

International Nuclear Information System (INIS)

Chang, Y.-C.; Lin, F.-A.; Lin, C.H.

2005-01-01

This paper proposes a method for using the branch and bound (B and B) method to solve the optimal chiller sequencing (OCS) problem and to eliminate the deficiencies of conventional methods. The coefficient of performance (COP) of the chiller is adopted as the objective function because it is concave. The Lagrangian method determines the optimal chiller loading (OCL) in each feasible state. The potential performance of the proposed method is examined with reference to an example system. The proposed method consumes much less power than the conventional method and is very appropriate for application in air conditioning systems

An O(m log n) algorithm for stuttering equivalence and branching bisimulation

NARCIS (Netherlands)

Groote, J.F.; Wijs, A.J.; Chechik, M.; Raskin, J.-F.

2016-01-01

We provide a new algorithm to determine stuttering equivalence with time complexity O(m log n), where n is the number of states and m is the number of transitions of a Kripke structure. This algorithm can also be used to determine branching bisimulation in O(m(log|Act|+log n)) time. Theoretically,

An O(mlog n) algorithm for computing stuttering equivalence and branching bisimulation

NARCIS (Netherlands)

Groote, J.F.; Jansen, D.N.; Keiren, J.J.A.; Wijs, A.J.

2017-01-01

We provide a new algorithm to determine stuttering equivalence with time complexity O(mlog n), where n is the number of states and mis the number of transitions of a Kripke structure. This algorithm can also be used to determine branching bisimulation in O(m(log |Act| + log n)) time, where Act is

Computational experience with a parallel algorithm for tetrangle inequality bound smoothing.

Science.gov (United States)

Rajan, K; Deo, N

1999-09-01

Determining molecular structure from interatomic distances is an important and challenging problem. Given a molecule with n atoms, lower and upper bounds on interatomic distances can usually be obtained only for a small subset of the 2(n(n-1)) atom pairs, using NMR. Given the bounds so obtained on the distances between some of the atom pairs, it is often useful to compute tighter bounds on all the 2(n(n-1)) pairwise distances. This process is referred to as bound smoothing. The initial lower and upper bounds for the pairwise distances not measured are usually assumed to be 0 and infinity. One method for bound smoothing is to use the limits imposed by the triangle inequality. The distance bounds so obtained can often be tightened further by applying the tetrangle inequality--the limits imposed on the six pairwise distances among a set of four atoms (instead of three for the triangle inequalities). The tetrangle inequality is expressed by the Cayley-Menger determinants. For every quadruple of atoms, each pass of the tetrangle inequality bound smoothing procedure finds upper and lower limits on each of the six distances in the quadruple. Applying the tetrangle inequalities to each of the (4n) quadruples requires O(n4) time. Here, we propose a parallel algorithm for bound smoothing employing the tetrangle inequality. Each pass of our algorithm requires O(n3 log n) time on a REW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) with O(log(n)n) processors. An implementation of this parallel algorithm on the Intel Paragon XP/S and its performance are also discussed.

Exact parallel maximum clique algorithm for general and protein graphs.

Science.gov (United States)

Depolli, Matjaž; Konc, Janez; Rozman, Kati; Trobec, Roman; Janežič, Dušanka

2013-09-23

A new exact parallel maximum clique algorithm MaxCliquePara, which finds the maximum clique (the fully connected subgraph) in undirected general and protein graphs, is presented. First, a new branch and bound algorithm for finding a maximum clique on a single computer core, which builds on ideas presented in two published state of the art sequential algorithms is implemented. The new sequential MaxCliqueSeq algorithm is faster than the reference algorithms on both DIMACS benchmark graphs as well as on protein-derived product graphs used for protein structural comparisons. Next, the MaxCliqueSeq algorithm is parallelized by splitting the branch-and-bound search tree to multiple cores, resulting in MaxCliquePara algorithm. The ability to exploit all cores efficiently makes the new parallel MaxCliquePara algorithm markedly superior to other tested algorithms. On a 12-core computer, the parallelization provides up to 2 orders of magnitude faster execution on the large DIMACS benchmark graphs and up to an order of magnitude faster execution on protein product graphs. The algorithms are freely accessible on http://commsys.ijs.si/~matjaz/maxclique.

Tolerance based algorithms for the ATSP

NARCIS (Netherlands)

Goldengorin, B; Sierksma, G; Turkensteen, M; Hromkovic, J; Nagl, M; Westfechtel, B

2004-01-01

In this paper we use arc tolerances, instead of arc costs, to improve Branch-and-Bound type algorithms for the Asymmetric Traveling Salesman Problem (ATSP). We derive new tighter lower bounds based on exact and approximate bottleneck upper tolerance values of the Assignment Problem (AP). It is shown

An Algorithm for the Weighted Earliness-Tardiness Unconstrained Project Scheduling Problem

Science.gov (United States)

Afshar Nadjafi, Behrouz; Shadrokh, Shahram

This research considers a project scheduling problem with the object of minimizing weighted earliness-tardiness penalty costs, taking into account a deadline for the project and precedence relations among the activities. An exact recursive method has been proposed for solving the basic form of this problem. We present a new depth-first branch and bound algorithm for extended form of the problem, which time value of money is taken into account by discounting the cash flows. The algorithm is extended with two bounding rules in order to reduce the size of the branch and bound tree. Finally, some test problems are solved and computational results are reported.

Algorithms for polynomial spectral factorization and bounded-real balanced state space representations

NARCIS (Netherlands)

Rapisarda, P.; Trentelman, H.L.; Minh, H.B.

We illustrate an algorithm that starting from the image representation of a strictly bounded-real system computes a minimal balanced state variable, from which a minimal balanced state realization is readily obtained. The algorithm stems from an iterative procedure to compute a storage function,

Capacitated Bounded Cardinality Hub Routing Problem: Model and Solution Algorithm

OpenAIRE

Gelareha, Shahin; Monemic, Rahimeh Neamatian; Semetd, Frederic

2017-01-01

In this paper, we address the Bounded Cardinality Hub Location Routing with Route Capacity wherein each hub acts as a transshipment node for one directed route. The number of hubs lies between a minimum and a maximum and the hub-level network is a complete subgraph. The transshipment operations take place at the hub nodes and flow transfer time from a hub-level transporter to a spoke-level vehicle influences spoke- to-hub allocations. We propose a mathematical model and a branch-and-cut algor...

New Facets and a Branch-and-Cut Algorithm for the Weighted Clique Problem

DEFF Research Database (Denmark)

Sørensen, Michael Malmros

2001-01-01

of facet defining inequalities in a branch-and-cut algorithm for the problem. We give a description of this algorithm, including some separation procedures, and present the computational results for different sets of test problems. The computation times that are obtained indicate that this algorithm...... four new classes of facet defining inequalities for the associated b-clique polytope. One of these inequality classes constitutes a generalization of the well known tree inequalities; the other classes are associated with multistars. We utilize these inequality classes together with other classes...... is more efficient than previously described algorithms for the problem....

New facets and a branch-and-cut algorithm for the weighted clique problem

DEFF Research Database (Denmark)

Sørensen, Michael Malmros

2004-01-01

four new classes of facet defining inequalities for the associated b-clique polytope. One of these inequality classes constitutes a generalization of the well known tree inequalities; the other classes are associated with multistars. We use these inequalities together with other classes of facet...... defining inequalities in a branch-and-cut algorithm for the problem. We give a description of this algorithm, including some separation procedures, and present the computational results for different sets of test problems. The computation times that are obtained indicate that this algorithm is more...

Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax

DEFF Research Database (Denmark)

Krejca, Martin S.; Witt, Carsten

2017-01-01

The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, on its expected run time is proved...... values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general........ This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit...

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

DEFF Research Database (Denmark)

Friedmann, Oliver; Hansen, Thomas Dueholm; Zwick, Uri

2011-01-01

The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. With essentially all deterministic pivoting rules it is known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior...... to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2Ω(nα), for some α>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date. The first randomized pivoting rule considered is Random-Edge, which among all improving...... pivoting steps (or edges) from the current basic feasible solution (or vertex) chooses one uniformly at random. The second randomized pivoting rule considered is Random-Facet, a more complicated randomized pivoting rule suggested by Kalai and by Matousek, Sharir and Welzl. Our lower bound for the Random...

An improved cut-and-solve algorithm for the single-source capacitated facility location problem

DEFF Research Database (Denmark)

Gadegaard, Sune Lauth; Klose, Andreas; Nielsen, Lars Relund

2018-01-01

In this paper, we present an improved cut-and-solve algorithm for the single-source capacitated facility location problem. The algorithm consists of three phases. The first phase strengthens the integer program by a cutting plane algorithm to obtain a tight lower bound. The second phase uses a two......-level local branching heuristic to find an upper bound, and if optimality has not yet been established, the third phase uses the cut-and-solve framework to close the optimality gap. Extensive computational results are reported, showing that the proposed algorithm runs 10–80 times faster on average compared...

Exponential Lower Bounds for the PPSZ k-SAT Algorithm

DEFF Research Database (Denmark)

Chen, Shiteng; Scheder, Dominik Alban; Talebanfard, Navid

2013-01-01

In 1998, Paturi, Pudl´ak, Saks, and Zane presented PPSZ, an elegant randomized algorithm for k-SAT. Fourteen years on, this algorithm is still the fastest known worst-case algorithm. They proved that its expected running time on k-CNF formulas with n variables is at most 2(1−k)n, where k 2 (1/k).......). So far, no exponential lower bounds at all have been known. In this paper, we construct hard instances for PPSZ. That is, we construct satisfiable k-CNF formulas over n variables on which the expected running time is at least 2(1−k)n, for k 2 O(log2 k/k)....

Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost Cycles

DEFF Research Database (Denmark)

Hansen, Thomas Dueholm; Zwick, Uri

2010-01-01

Mean-Cost cycles (MMCC). Experimental studies suggest that Howard’s algorithm works extremely well in this context. The theoretical complexity of Howard’s algorithm for finding MMCCs is a mystery. No polynomial time bound is known on its running time. Prior to this work, there were only linear lower...

High-Speed Rail Train Timetabling Problem: A Time-Space Network Based Method with an Improved Branch-and-Price Algorithm

Directory of Open Access Journals (Sweden)

Bisheng He

2014-01-01

Full Text Available A time-space network based optimization method is designed for high-speed rail train timetabling problem to improve the service level of the high-speed rail. The general time-space path cost is presented which considers both the train travel time and the high-speed rail operation requirements: (1 service frequency requirement; (2 stopping plan adjustment; and (3 priority of train types. Train timetabling problem based on time-space path aims to minimize the total general time-space path cost of all trains. An improved branch-and-price algorithm is applied to solve the large scale integer programming problem. When dealing with the algorithm, a rapid branching and node selection for branch-and-price tree and a heuristic train time-space path generation for column generation are adopted to speed up the algorithm computation time. The computational results of a set of experiments on China’s high-speed rail system are presented with the discussions about the model validation, the effectiveness of the general time-space path cost, and the improved branch-and-price algorithm.

A branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem

NARCIS (Netherlands)

K. Dalmeijer (Kevin); R. Spliet (Remy)

2016-01-01

textabstractThis paper presents a branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem (TWAVRP), the problem of assigning time windows for delivery before demand volume becomes known. A novel set of valid inequalities, the precedence inequalities, is introduced and

Unified solution of a non-convex SCUC problem using combination of modified Branch-and-Bound method with Quadratic Programming

International Nuclear Information System (INIS)

Shafie-khah, M.; Parsa Moghaddam, M.; Sheikh-El-Eslami, M.K.

2011-01-01

Highlights: → A hybrid SCUC solution is developed to deal with large-scale, real-time and long-term problems. → New formulations are proposed for considering valve point effect and warmth-dependent start-up cost. → A new algorithm is developed for modeling the AC power flow in SCUC problems. → Using the power flow algorithm both steps in traditional SCUC is done simultaneously. → The proposed method provides better solutions than previous ones with a fast speed. - Abstract: In this paper, a new practical method is presented for solving the non-convex security constraint unit commitment (SCUC) problem in power systems. The accuracy of the proposed method is desirable while the shorter computation time makes it useful for SCUC solution of large-scale power systems, real-time market operation and long-term SCUC problems. The proposed framework allows inclusion of the valve point effects, warmth-dependent start-up costs, ramp rates, minimum up/down time constraints, multiple fuels costs, emission costs, prohibited operating zones and AC power flow limits in normal and contingency conditions. To solve the non-convex problem, combination of a modified Branch-and-Bound method with the Quadratic Programming is used as an optimization tool and a developed AC power flow algorithm is applied for considering the security and contingency concerns using the nonlinear/linear AC model. These modifications improve the convergence speed and solution precision of SCUC problem. In the proposed method, in contrast with traditional SCUC algorithms, unit commitment solution, checking and satisfying the security constraints are managed simultaneously. The obtained results are compared with other reported methods for investigating the effectiveness of the proposed method. Also, the proposed method is applied to an Iranian power system including 493 thermal units.

A tighter bound for the self-stabilization time in Hermanʼs algorithm

DEFF Research Database (Denmark)

Feng, Yuan; Zhang, Lijun

2013-01-01

We study the expected self-stabilization time of Hermanʼs algorithm. For N processors the lower bound is 427N2 (0.148N2), and an upper bound of 0.64N2 is presented in Kiefer et al. (2011) [4]. In this paper we give a tighter upper bound 0.521N2. © 2013 Published by Elsevier B.V....

A Global Optimization Algorithm for Sum of Linear Ratios Problem

Directory of Open Access Journals (Sweden)

Yuelin Gao

2013-01-01

Full Text Available We equivalently transform the sum of linear ratios programming problem into bilinear programming problem, then by using the linear characteristics of convex envelope and concave envelope of double variables product function, linear relaxation programming of the bilinear programming problem is given, which can determine the lower bound of the optimal value of original problem. Therefore, a branch and bound algorithm for solving sum of linear ratios programming problem is put forward, and the convergence of the algorithm is proved. Numerical experiments are reported to show the effectiveness of the proposed algorithm.

Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time Windows

DEFF Research Database (Denmark)

Røpke, Stefan; Cordeau, Jean-Francois

2009-01-01

In the pickup and delivery problem with time windows (PDPTW), vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and a delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch......-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and a non-elementary shortest path problem. Valid inequalities...

Higher order branching of periodic orbits from polynomial isochrones

Directory of Open Access Journals (Sweden)

B. Toni

1999-09-01

Full Text Available We discuss the higher order local bifurcations of limit cycles from polynomial isochrones (linearizable centers when the linearizing transformation is explicitly known and yields a polynomial perturbation one-form. Using a method based on the relative cohomology decomposition of polynomial one-forms complemented with a step reduction process, we give an explicit formula for the overall upper bound of branch points of limit cycles in an arbitrary $n$ degree polynomial perturbation of the linear isochrone, and provide an algorithmic procedure to compute the upper bound at successive orders. We derive a complete analysis of the nonlinear cubic Hamiltonian isochrone and show that at most nine branch points of limit cycles can bifurcate in a cubic polynomial perturbation. Moreover, perturbations with exactly two, three, four, six, and nine local families of limit cycles may be constructed.

A branch-and-cut-and-price algorithm for the mixed capacitated general routing problem

DEFF Research Database (Denmark)

Bach, Lukas; Wøhlk, Sanne; Lysgaard, Jens

2016-01-01

In this paper, we consider the Mixed Capacitated General Routing Problem which is a combination of the Capacitated Vehicle Routing Problem and the Capacitated Arc Routing Problem. The problem is also known as the Node, Edge, and Arc Routing Problem. We propose a Branch-and-Cut-and-Price algorithm...

Solution Algorithm for a New Bi-Level Discrete Network Design Problem

Directory of Open Access Journals (Sweden)

Qun Chen

2013-12-01

Full Text Available A new discrete network design problem (DNDP was pro-posed in this paper, where the variables can be a series of integers rather than just 0-1. The new DNDP can determine both capacity improvement grades of reconstruction roads and locations and capacity grades of newly added roads, and thus complies with the practical projects where road capacity can only be some discrete levels corresponding to the number of lanes of roads. This paper designed a solution algorithm combining branch-and-bound with Hooke-Jeeves algorithm, where feasible integer solutions are recorded in searching the process of Hooke-Jeeves algorithm, lend -ing itself to determine the upper bound of the upper-level problem. The thresholds for branch cutting and ending were set for earlier convergence. Numerical examples are given to demonstrate the efficiency of the proposed algorithm.

Rigorous lower bound on the dynamic critical exponent of some multilevel Swendsen-Wang algorithms

International Nuclear Information System (INIS)

Li, X.; Sokal, A.D.

1991-01-01

We prove the rigorous lower bound z exp ≥α/ν for the dynamic critical exponent of a broad class of multilevel (or ''multigrid'') variants of the Swendsen-Wang algorithm. This proves that such algorithms do suffer from critical slowing down. We conjecture that such algorithms in fact lie in the same dynamic universality class as the stanard Swendsen-Wang algorithm

Algorithmic test design using classical item parameters

NARCIS (Netherlands)

van der Linden, Willem J.; Adema, Jos J.

Two optimalization models for the construction of tests with a maximal value of coefficient alpha are given. Both models have a linear form and can be solved by using a branch-and-bound algorithm. The first model assumes an item bank calibrated under the Rasch model and can be used, for instance,

Algorithms for optimization of branching gravity-driven water networks

Directory of Open Access Journals (Sweden)

I. Dardani

2018-05-01

Full Text Available The design of a water network involves the selection of pipe diameters that satisfy pressure and flow requirements while considering cost. A variety of design approaches can be used to optimize for hydraulic performance or reduce costs. To help designers select an appropriate approach in the context of gravity-driven water networks (GDWNs, this work assesses three cost-minimization algorithms on six moderate-scale GDWN test cases. Two algorithms, a backtracking algorithm and a genetic algorithm, use a set of discrete pipe diameters, while a new calculus-based algorithm produces a continuous-diameter solution which is mapped onto a discrete-diameter set. The backtracking algorithm finds the global optimum for all but the largest of cases tested, for which its long runtime makes it an infeasible option. The calculus-based algorithm's discrete-diameter solution produced slightly higher-cost results but was more scalable to larger network cases. Furthermore, the new calculus-based algorithm's continuous-diameter and mapped solutions provided lower and upper bounds, respectively, on the discrete-diameter global optimum cost, where the mapped solutions were typically within one diameter size of the global optimum. The genetic algorithm produced solutions even closer to the global optimum with consistently short run times, although slightly higher solution costs were seen for the larger network cases tested. The results of this study highlight the advantages and weaknesses of each GDWN design method including closeness to the global optimum, the ability to prune the solution space of infeasible and suboptimal candidates without missing the global optimum, and algorithm run time. We also extend an existing closed-form model of Jones (2011 to include minor losses and a more comprehensive two-part cost model, which realistically applies to pipe sizes that span a broad range typical of GDWNs of interest in this work, and for smooth and commercial steel

Algorithms for optimization of branching gravity-driven water networks

Science.gov (United States)

Dardani, Ian; Jones, Gerard F.

2018-05-01

The design of a water network involves the selection of pipe diameters that satisfy pressure and flow requirements while considering cost. A variety of design approaches can be used to optimize for hydraulic performance or reduce costs. To help designers select an appropriate approach in the context of gravity-driven water networks (GDWNs), this work assesses three cost-minimization algorithms on six moderate-scale GDWN test cases. Two algorithms, a backtracking algorithm and a genetic algorithm, use a set of discrete pipe diameters, while a new calculus-based algorithm produces a continuous-diameter solution which is mapped onto a discrete-diameter set. The backtracking algorithm finds the global optimum for all but the largest of cases tested, for which its long runtime makes it an infeasible option. The calculus-based algorithm's discrete-diameter solution produced slightly higher-cost results but was more scalable to larger network cases. Furthermore, the new calculus-based algorithm's continuous-diameter and mapped solutions provided lower and upper bounds, respectively, on the discrete-diameter global optimum cost, where the mapped solutions were typically within one diameter size of the global optimum. The genetic algorithm produced solutions even closer to the global optimum with consistently short run times, although slightly higher solution costs were seen for the larger network cases tested. The results of this study highlight the advantages and weaknesses of each GDWN design method including closeness to the global optimum, the ability to prune the solution space of infeasible and suboptimal candidates without missing the global optimum, and algorithm run time. We also extend an existing closed-form model of Jones (2011) to include minor losses and a more comprehensive two-part cost model, which realistically applies to pipe sizes that span a broad range typical of GDWNs of interest in this work, and for smooth and commercial steel roughness values.

A Global Optimization Algorithm for Sum of Linear Ratios Problem

OpenAIRE

Yuelin Gao; Siqiao Jin

2013-01-01

We equivalently transform the sum of linear ratios programming problem into bilinear programming problem, then by using the linear characteristics of convex envelope and concave envelope of double variables product function, linear relaxation programming of the bilinear programming problem is given, which can determine the lower bound of the optimal value of original problem. Therefore, a branch and bound algorithm for solving sum of linear ratios programming problem is put forward, and the c...

A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem

DEFF Research Database (Denmark)

Wøhlk, Sanne; Lysgaard, Jens

2014-01-01

The paper considers the Cumulative Capacitated Vehicle Routing Problem (CCVRP), which is a variation of the well-known Capacitated Vehicle Routing Problem (CVRP). In this problem, the traditional objective of minimizing total distance or time traveled by the vehicles is replaced by minimizing...... the sum of arrival times at the customers. A branch-and-cut-and-price algorithm for obtaining optimal solutions to the problem is proposed. Computational results based on a set of standard CVRP benchmarks are presented....

Upper-Lower Bounds Candidate Sets Searching Algorithm for Bayesian Network Structure Learning

Directory of Open Access Journals (Sweden)

Guangyi Liu

2014-01-01

Full Text Available Bayesian network is an important theoretical model in artificial intelligence field and also a powerful tool for processing uncertainty issues. Considering the slow convergence speed of current Bayesian network structure learning algorithms, a fast hybrid learning method is proposed in this paper. We start with further analysis of information provided by low-order conditional independence testing, and then two methods are given for constructing graph model of network, which is theoretically proved to be upper and lower bounds of the structure space of target network, so that candidate sets are given as a result; after that a search and scoring algorithm is operated based on the candidate sets to find the final structure of the network. Simulation results show that the algorithm proposed in this paper is more efficient than similar algorithms with the same learning precision.

Control Theoretical Expression of Quantum Systems And Lower Bound of Finite Horizon Quantum Algorithms

OpenAIRE

Yanagisawa, Masahiro

2007-01-01

We provide a control theoretical method for a computational lower bound of quantum algorithms based on quantum walks of a finite time horizon. It is shown that given a quantum network, there exists a control theoretical expression of the quantum system and the transition probability of the quantum walk is related to a norm of the associated transfer function.

Computational results with a branch and cut code for the capacitated vehicle routing problem

Energy Technology Data Exchange (ETDEWEB)

Augerat, P.; Naddef, D. [Institut National Polytechnique, 38 - Grenoble (France); Belenguer, J.M.; Benavent, E.; Corberan, A. [Valencia Univ. (Spain); Rinaldi, G. [Consiglio Nazionale delle Ricerche, Rome (Italy)

1995-09-01

The Capacitated Vehicle Routing Problem (CVRP) we consider in this paper consists in the optimization of the distribution of goods from a single depot to a given set of customers with known demand using a given number of vehicles of fixed capacity. There are many practical routing applications in the public sector such as school bus routing, pick up and mail delivery, and in the private sector such as the dispatching of delivery trucks. We present a Branch and Cut algorithm to solve the CVRP which is based in the partial polyhedral description of the corresponding polytope. The valid inequalities used in our method can ne found in Cornuejols and Harche (1993), Harche and Rinaldi (1991) and in Augerat and Pochet (1995). We concentrated mainly on the design of separation procedures for several classes of valid inequalities. The capacity constraints (generalized sub-tour eliminations inequalities) happen to play a crucial role in the development of a cutting plane algorithm for the CVRP. A large number of separation heuristics have been implemented and compared for these inequalities. There has been also implemented heuristic separation algorithms for other classes of valid inequalities that also lead to significant improvements: comb and extended comb inequalities, generalized capacity inequalities and hypo-tour inequalities. The resulting cutting plane algorithm has been applied to a set of instances taken from the literature and the lower bounds obtained are better than the ones previously known. Some branching strategies have been implemented to develop a Branch an Cut algorithm that has been able to solve large CVRP instances, some of them which had never been solved before. (authors). 32 refs., 3 figs., 10 tabs.

First direct observation of bound-state beta-decay: Measurements of branching and lifetime of 207Tl81+ fragments

International Nuclear Information System (INIS)

Boutin, D.

2005-08-01

The first experimental observation of bound-state beta-decay showed, that due solely to the electron stripping, a stable nuclide, e.g. 163 Dy, became unstable. Also a drastic modification of the half-life of bare 187 Re, from 4.12(2) x 10 10 years down to 32.9(20) years, could be observed. It was mainly due to the possibility for the mother nuclide to decay into a previously inaccessible nuclear level of the daughter nuclide. It was proposed to study a nuclide where this decay mode was competing with continuum-state beta-decay, in order to measure their respective branchings. The ratio β b /β c could also be evaluated for the first time. 207 Tl was chosen due to its high atomic number, and Q-value of about 1.4 MeV, small enough to enhance the β b probability and large enough to allow the use of time-resolved Schottky Mass Spectrometry (SMS) to study the evolution of mother and bound-state beta-decay daughter ions. The decay properties of the ground state and isomeric state of 207 Tl 81+ have been investigated at the GSI accelerator facility in two separate experiments. For the first time β-decay where the electron could go either to a bound state (atomic orbitals) and lead to 207 Pb 81+ as a daughter nuclide, or to a continuum state and lead to 207 Pb 82+ , has been observed. The respective branchings of these two processes could be measured as well. The deduced total nuclear half-life of 255(17) s for 207 Tl 81+ , was slightly modified with respect to the half-life of the neutral atom of 286(2) s. It was nevertheless in very good agreement with calculations based on the assumption that the beta-decay was following an allowed type of transition. The branching β b /β c =0.192(20), was also in very good agreement with the same calculations. The application of stochastic precooling allowed to observe in addition the 1348 keV short-lived isomeric state of 207 Tl. The half-life of this isomeric state was measured as 1.47(32) s, which shows a small deviation

An Interval Bound Algorithm of optimizing reactor core loading pattern by using reactivity interval schema

International Nuclear Information System (INIS)

Gong Zhaohu; Wang Kan; Yao Dong

2011-01-01

Highlights: → We present a new Loading Pattern Optimization method - Interval Bound Algorithm (IBA). → IBA directly uses the reactivity of fuel assemblies and burnable poison. → IBA can optimize fuel assembly orientation in a coupled way. → Numerical experiment shows that IBA outperforms genetic algorithm and engineers. → We devise DDWF technique to deal with multiple objectives and constraints. - Abstract: In order to optimize the core loading pattern in Nuclear Power Plants, the paper presents a new optimization method - Interval Bound Algorithm (IBA). Similar to the typical population based algorithms, e.g. genetic algorithm, IBA maintains a population of solutions and evolves them during the optimization process. IBA acquires the solution by statistical learning and sampling the control variable intervals of the population in each iteration. The control variables are the transforms of the reactivity of fuel assemblies or the worth of burnable poisons, which are the crucial heuristic information for loading pattern optimization problems. IBA can deal with the relationship between the dependent variables by defining the control variables. Based on the IBA algorithm, a parallel Loading Pattern Optimization code, named IBALPO, has been developed. To deal with multiple objectives and constraints, the Dynamic Discontinuous Weight Factors (DDWF) for the fitness function have been used in IBALPO. Finally, the code system has been used to solve a realistic reloading problem and a better pattern has been obtained compared with the ones searched by engineers and genetic algorithm, thus the performance of the code is proved.

Can abnormal returns be earned on bandwidth-bounded currencies? Evidence from a genetic algorithm

OpenAIRE

Pedro Godinho

2012-01-01

Most of the studies about the Foreign Exchange market (Forex) analyse the behaviour of currencies that are allowed to float freely (or almost freely), but some currencies are still bounded by bandwidths (either disclosed or undisclosed). In this paper, I try to find out whether two bandwidth-bounded currencies, the Hong Kong dollar (HKD) and the Singapore dollar (SGD), present opportunities for abnormal returns. I consider a set of trading rules, and I use a genetic algorithm to optimise both...

The DMM Bound

DEFF Research Database (Denmark)

Emiris, Ioannis Z.; Mourrain, Bernard; Tsigaridas, Elias

2010-01-01

) resultant by means of mixed volume, as well as recent advances on aggregate root bounds for univariate polynomials, and are applicable to arbitrary positive dimensional systems. We improve upon Canny's gap theorem [7] by a factor of O(dn-1), where d bounds the degree of the polynomials, and n is the number...... bound on the number of steps that subdivision-based algorithms perform in order to isolate all real roots of a polynomial system. This leads to the first complexity bound of Milne's algorithm [22] in 2D....

New matrix bounds and iterative algorithms for the discrete coupled algebraic Riccati equation

Science.gov (United States)

Liu, Jianzhou; Wang, Li; Zhang, Juan

2017-11-01

The discrete coupled algebraic Riccati equation (DCARE) has wide applications in control theory and linear system. In general, for the DCARE, one discusses every term of the coupled term, respectively. In this paper, we consider the coupled term as a whole, which is different from the recent results. When applying eigenvalue inequalities to discuss the coupled term, our method has less error. In terms of the properties of special matrices and eigenvalue inequalities, we propose several upper and lower matrix bounds for the solution of DCARE. Further, we discuss the iterative algorithms for the solution of the DCARE. In the fixed point iterative algorithms, the scope of Lipschitz factor is wider than the recent results. Finally, we offer corresponding numerical examples to illustrate the effectiveness of the derived results.

General upper bounds on the runtime of parallel evolutionary algorithms.

Science.gov (United States)

Lässig, Jörg; Sudholt, Dirk

2014-01-01

We present a general method for analyzing the runtime of parallel evolutionary algorithms with spatially structured populations. Based on the fitness-level method, it yields upper bounds on the expected parallel runtime. This allows for a rigorous estimate of the speedup gained by parallelization. Tailored results are given for common migration topologies: ring graphs, torus graphs, hypercubes, and the complete graph. Example applications for pseudo-Boolean optimization show that our method is easy to apply and that it gives powerful results. In our examples the performance guarantees improve with the density of the topology. Surprisingly, even sparse topologies such as ring graphs lead to a significant speedup for many functions while not increasing the total number of function evaluations by more than a constant factor. We also identify which number of processors lead to the best guaranteed speedups, thus giving hints on how to parameterize parallel evolutionary algorithms.

Perceptron Mistake Bounds

OpenAIRE

Mohri, Mehryar; Rostamizadeh, Afshin

2013-01-01

We present a brief survey of existing mistake bounds and introduce novel bounds for the Perceptron or the kernel Perceptron algorithm. Our novel bounds generalize beyond standard margin-loss type bounds, allow for any convex and Lipschitz loss function, and admit a very simple proof.

HiggsBounds-4. Improved tests of extended Higgs sectors against exclusion bounds from LEP, the Tevatron and the LHC

Energy Technology Data Exchange (ETDEWEB)

Bechtle, Philip [Bonn Univ. (Germany). Physikalisches Inst.; Heinemeyer, Sven [Instituto de Fisica de Cantabria (CSIC-UC), Santander (Spain); Staal, Oscar [Stockholm Univ. (Sweden). Dept. of Physics; Stefaniak, Tim; Williams, Karina E. [Bonn Univ. (Germany). Physikalisches Inst.; Bonn Univ. (Germany). Bethe Center for Theoretical Physics; Weiglein, Georg [Deutsches Elektronen-Synchrotron (DESY), Hamburg (Germany); Brein, Oliver

2013-12-15

We describe the new developments in version 4 of the public computer code HiggsBounds. HiggsBounds is a tool to test models with arbitrary Higgs sectors, containing both neutral and charged Higgs bosons, against the published exclusion bounds from Higgs searches at the LEP, Tevatron and LHC experiments. From the model predictions for the Higgs masses, branching ratios, production cross sections and total decay widths - which are specified by the user in the input for the program - the code calculates the predicted signal rates for the search channels considered in the experimental data. The signal rates are compared to the expected and observed cross section limits from the Higgs searches to determine whether a point in the model parameter space is excluded at 95% confidence level. In this paper we present a modification of the HiggsBounds main algorithm that extends the exclusion test in order to ensure that it provides useful results in the presence of one or more significant excesses in the data, corresponding to potential Higgs signals. We also describe a new method to test whether the limits from an experimental search performed under certain model assumptions can be applied to a different theoretical model. Further developments discussed here include a framework to take into account theoretical uncertainties on the Higgs mass predictions, and the possibility to obtain the {chi}{sup 2} likelihood of Higgs exclusion limits from LEP. Extensions to the user subroutines from earlier versions of HiggsBounds are described. The new features are demonstrated by additional example programs.

HiggsBounds-4. Improved tests of extended Higgs sectors against exclusion bounds from LEP, the Tevatron and the LHC

International Nuclear Information System (INIS)

Bechtle, Philip; Staal, Oscar; Brein, Oliver

2013-12-01

We describe the new developments in version 4 of the public computer code HiggsBounds. HiggsBounds is a tool to test models with arbitrary Higgs sectors, containing both neutral and charged Higgs bosons, against the published exclusion bounds from Higgs searches at the LEP, Tevatron and LHC experiments. From the model predictions for the Higgs masses, branching ratios, production cross sections and total decay widths - which are specified by the user in the input for the program - the code calculates the predicted signal rates for the search channels considered in the experimental data. The signal rates are compared to the expected and observed cross section limits from the Higgs searches to determine whether a point in the model parameter space is excluded at 95% confidence level. In this paper we present a modification of the HiggsBounds main algorithm that extends the exclusion test in order to ensure that it provides useful results in the presence of one or more significant excesses in the data, corresponding to potential Higgs signals. We also describe a new method to test whether the limits from an experimental search performed under certain model assumptions can be applied to a different theoretical model. Further developments discussed here include a framework to take into account theoretical uncertainties on the Higgs mass predictions, and the possibility to obtain the χ 2 likelihood of Higgs exclusion limits from LEP. Extensions to the user subroutines from earlier versions of HiggsBounds are described. The new features are demonstrated by additional example programs.

A Linearized Relaxing Algorithm for the Specific Nonlinear Optimization Problem

Directory of Open Access Journals (Sweden)

Mio Horai

2016-01-01

Full Text Available We propose a new method for the specific nonlinear and nonconvex global optimization problem by using a linear relaxation technique. To simplify the specific nonlinear and nonconvex optimization problem, we transform the problem to the lower linear relaxation form, and we solve the linear relaxation optimization problem by the Branch and Bound Algorithm. Under some reasonable assumptions, the global convergence of the algorithm is certified for the problem. Numerical results show that this method is more efficient than the previous methods.

Length-Bounded Hybrid CPU/GPU Pattern Matching Algorithm for Deep Packet Inspection

Directory of Open Access Journals (Sweden)

Yi-Shan Lin

2017-01-01

Full Text Available Since frequent communication between applications takes place in high speed networks, deep packet inspection (DPI plays an important role in the network application awareness. The signature-based network intrusion detection system (NIDS contains a DPI technique that examines the incoming packet payloads by employing a pattern matching algorithm that dominates the overall inspection performance. Existing studies focused on implementing efficient pattern matching algorithms by parallel programming on software platforms because of the advantages of lower cost and higher scalability. Either the central processing unit (CPU or the graphic processing unit (GPU were involved. Our studies focused on designing a pattern matching algorithm based on the cooperation between both CPU and GPU. In this paper, we present an enhanced design for our previous work, a length-bounded hybrid CPU/GPU pattern matching algorithm (LHPMA. In the preliminary experiment, the performance and comparison with the previous work are displayed, and the experimental results show that the LHPMA can achieve not only effective CPU/GPU cooperation but also higher throughput than the previous method.

Avoiding spurious submovement decompositions: a globally optimal algorithm

International Nuclear Information System (INIS)

Rohrer, Brandon Robinson; Hogan, Neville

2003-01-01

Evidence for the existence of discrete submovements underlying continuous human movement has motivated many attempts to extract them. Although they produce visually convincing results, all of the methodologies that have been employed are prone to produce spurious decompositions. Examples of potential failures are given. A branch-and-bound algorithm for submovement extraction, capable of global nonlinear minimization (and hence capable of avoiding spurious decompositions), is developed and demonstrated.

Reconciling taxonomy and phylogenetic inference: formalism and algorithms for describing discord and inferring taxonomic roots

Directory of Open Access Journals (Sweden)

Matsen Frederick A

2012-05-01

Full Text Available Abstract Background Although taxonomy is often used informally to evaluate the results of phylogenetic inference and the root of phylogenetic trees, algorithmic methods to do so are lacking. Results In this paper we formalize these procedures and develop algorithms to solve the relevant problems. In particular, we introduce a new algorithm that solves a "subcoloring" problem to express the difference between a taxonomy and a phylogeny at a given rank. This algorithm improves upon the current best algorithm in terms of asymptotic complexity for the parameter regime of interest; we also describe a branch-and-bound algorithm that saves orders of magnitude in computation on real data sets. We also develop a formalism and an algorithm for rooting phylogenetic trees according to a taxonomy. Conclusions The algorithms in this paper, and the associated freely-available software, will help biologists better use and understand taxonomically labeled phylogenetic trees.

Application of Heuristic and Metaheuristic Algorithms in Solving Constrained Weber Problem with Feasible Region Bounded by Arcs

Directory of Open Access Journals (Sweden)

Igor Stojanović

2017-01-01

Full Text Available The continuous planar facility location problem with the connected region of feasible solutions bounded by arcs is a particular case of the constrained Weber problem. This problem is a continuous optimization problem which has a nonconvex feasible set of constraints. This paper suggests appropriate modifications of four metaheuristic algorithms which are defined with the aim of solving this type of nonconvex optimization problems. Also, a comparison of these algorithms to each other as well as to the heuristic algorithm is presented. The artificial bee colony algorithm, firefly algorithm, and their recently proposed improved versions for constrained optimization are appropriately modified and applied to the case study. The heuristic algorithm based on modified Weiszfeld procedure is also implemented for the purpose of comparison with the metaheuristic approaches. Obtained numerical results show that metaheuristic algorithms can be successfully applied to solve the instances of this problem of up to 500 constraints. Among these four algorithms, the improved version of artificial bee algorithm is the most efficient with respect to the quality of the solution, robustness, and the computational efficiency.

Solusi Optimal Model Optimisasi Robust Untuk Masalah Traveling Salesman Dengan Ketidaktentuan Kotak Dan Pendekatan Metode Branch And Bound

Directory of Open Access Journals (Sweden)

Poppy Amriyati

2015-12-01

Full Text Available Traveling Salesman Problem (TSP merupakan teknik pencarian rute yang dimulai dari satu titik awal, setiap kota harus dikunjungi sekali dan kemudian kembali ke tempat asal sehingga total jarak atau waktu perjalanan adalah minimum. Untuk mengatasi kedakpastian jarak atau waktu perjalanan, maka perlu dilakukan pengembangan model TSP. Salah satu bidang Optimisasi yang mampu menyelesaikan permasalahan terkait ketidakpastian adalah Optimisasi Robust. Dalam makalah ini dibahas mengenai penerapan Optimisasi Robust pada TSP (RTSP menggunakan pendekatan Box Uncertainty dan diselesaikan dengan menggunakan Metode Branch and Bound. Disajikan simulasi numerik pada software aplikasi Maple untuk beberapa kasus nyata terkait penerapan Optimisasi RTSP , seperti masalah manajemen konstruksi, penentuan jarak tempuh kota di Pulau Jawa, dan Penentuan Rute Mandiri Fun Run.

Upper and lower bounds for disadvantage factors as a test of algorithm used in a synthesis method

International Nuclear Information System (INIS)

Nanneh, M.M.; Ackroyd, R.T.

1991-01-01

A lower bound for the disadvantage factor of a lattice cell of arbitrary configuration is obtained using a finite element method which is based on a variational principle for the even-parity angular flux. An upper bound for the disadvantage factor is given by a finite element method using the complementary variational principle for the odd-parity angular flux. These theoretical results are illustrated by calculations for uranium/graphite and uranium/water lattices. As the approximations are refined the fluxes obtained by the first method tend towards the actual flux from below in the moderator, and from above in the fuel. These trends are reversed for the second method. This derivation of benchmarks for disadvantage factors has been undertaken primarily as a test of an important algorithm used by the authors in a method of synthesising transport solutions starting with a diffusion theory approximation. The algorithm is used to convert odd-parity approximations for the angular flux into even-parity approximations and vice versa. (author). 15 refs., 8 tabs., 9 figs

Upper and lower bounds for disadvantage factors as a test of an algorithm used in a synthesis method

International Nuclear Information System (INIS)

Ackroyd, R.T.; Nanneh, M.M.

1988-01-01

A lower bound for the disadvantage factor of a lattice cell of arbitrary configuration is obtained using a finite element method which is based on a variational principle for the even-parity angular flux. An upper bound for the disadvantage factor is given by a finite element method using the complementary variational principle for the odd-parity angular flux. These theoretical results are illustrated by calculations for urnaium/graphite and uranium/water lattices. As the approximations are refined the fluxes obtained by the first method tend towards the actual flux from below in the moderator, and from above in the fuel. These trends are reversed for the second method. This derivation of benchmarks for disadvantage factors has been undertaken primarily as a test of an important algorithm used by the authors in a method of synthesising transport solutions starting with a diffusion theory approximation. The algorithm is used to convert odd-parity approximations for the angular flux into even-parity approximations and vice versa. (author)

Solving Large Quadratic|Assignment Problems in Parallel

DEFF Research Database (Denmark)

Clausen, Jens; Perregaard, Michael

1997-01-01

and recalculation of bounds between branchings when used in a parallel Branch-and-Bound algorithm. The algorithm has been implemented on a 16-processor MEIKO Computing Surface with Intel i860 processors. Computational results from the solution of a number of large QAPs, including the classical Nugent 20...... processors, and have hence not been ideally suited for computations essentially involving non-vectorizable computations on integers.In this paper we investigate the combination of one of the best bound functions for a Branch-and-Bound algorithm (the Gilmore-Lawler bound) and various testing, variable binding...

First direct observation of bound-state beta-decay. Measurements of branching and lifetime of {sup 207}Tl{sup 81+} fragments

Energy Technology Data Exchange (ETDEWEB)

Boutin, D.

2005-08-01

The first experimental observation of bound-state beta-decay showed, that due solely to the electron stripping, a stable nuclide, e.g. {sup 163}Dy, became unstable. Also a drastic modification of the half-life of bare {sup 187}Re, from 4.12(2) x 10{sup 10} years down to 32.9(20) years, could be observed. It was mainly due to the possibility for the mother nuclide to decay into a previously inaccessible nuclear level of the daughter nuclide. It was proposed to study a nuclide where this decay mode was competing with continuum-state beta-decay, in order to measure their respective branchings. The ratio {beta}{sub b}/{beta}{sub c} could also be evaluated for the first time. {sup 207}Tl was chosen due to its high atomic number, and Q-value of about 1.4 MeV, small enough to enhance the {beta}{sub b} probability and large enough to allow the use of time-resolved Schottky Mass Spectrometry (SMS) to study the evolution of mother and bound-state beta-decay daughter ions. The decay properties of the ground state and isomeric state of {sup 207}Tl{sup 81+} have been investigated at the GSI accelerator facility in two separate experiments. For the first time {beta}-decay where the electron could go either to a bound state (atomic orbitals) and lead to {sup 207}Pb{sup 81+} as a daughter nuclide, or to a continuum state and lead to {sup 207}Pb{sup 82+}, has been observed. The respective branchings of these two processes could be measured as well. The deduced total nuclear half-life of 255(17) s for {sup 207}Tl{sup 81+}, was slightly modified with respect to the half-life of the neutral atom of 286(2) s. It was nevertheless in very good agreement with calculations based on the assumption that the beta-decay was following an allowed type of transition. The branching {beta}{sub b}/{beta}{sub c}=0.192(20), was also in very good agreement with the same calculations. The application of stochastic precooling allowed to observe in addition the 1348 keV short-lived isomeric state of {sup

BranchAnalysis2D/3D automates morphometry analyses of branching structures.

Science.gov (United States)

Srinivasan, Aditya; Muñoz-Estrada, Jesús; Bourgeois, Justin R; Nalwalk, Julia W; Pumiglia, Kevin M; Sheen, Volney L; Ferland, Russell J

2018-01-15

Morphometric analyses of biological features have become increasingly common in recent years with such analyses being subject to a large degree of observer bias, variability, and time consumption. While commercial software packages exist to perform these analyses, they are expensive, require extensive user training, and are usually dependent on the observer tracing the morphology. To address these issues, we have developed a broadly applicable, no-cost ImageJ plugin we call 'BranchAnalysis2D/3D', to perform morphometric analyses of structures with branching morphologies, such as neuronal dendritic spines, vascular morphology, and primary cilia. Our BranchAnalysis2D/3D algorithm allows for rapid quantification of the length and thickness of branching morphologies, independent of user tracing, in both 2D and 3D data sets. We validated the performance of BranchAnalysis2D/3D against pre-existing software packages using trained human observers and images from brain and retina. We found that the BranchAnalysis2D/3D algorithm outputs results similar to available software (i.e., Metamorph, AngioTool, Neurolucida), while allowing faster analysis times and unbiased quantification. BranchAnalysis2D/3D allows inexperienced observers to output results like a trained observer but more efficiently, thereby increasing the consistency, speed, and reliability of morphometric analyses. Copyright © 2017 Elsevier B.V. All rights reserved.

Single Machine Problem with Multi-Rate-Modifying Activities under a Time-Dependent Deterioration

Directory of Open Access Journals (Sweden)

M. Huang

2013-01-01

Full Text Available The single machine scheduling problem with multi-rate-modifying activities under a time-dependent deterioration to minimize makespan is studied. After examining the characteristics of the problem, a number of properties and a lower bound are proposed. A branch and bound algorithm and a heuristic algorithm are used in the solution, and two special cases are also examined. The computational experiments show that, for the situation with a rate-modifying activity, the proposed branch and bound algorithm can solve situations with 50 jobs within a reasonable time, and the heuristic algorithm can obtain the near-optimal solution with an error percentage less than 0.053 in a very short time. In situations with multi-rate-modifying activities, the proposed branch and bound algorithm can solve the case with 15 jobs within a reasonable time, and the heuristic algorithm can obtain the near-optimal with an error percentage less than 0.070 in a very short time. The branch and bound algorithm and the heuristic algorithm are both shown to be efficient and effective.

A Scalable GVT Estimation Algorithm for PDES: Using Lower Bound of Event-Bulk-Time

Directory of Open Access Journals (Sweden)

Yong Peng

2015-01-01

Full Text Available Global Virtual Time computation of Parallel Discrete Event Simulation is crucial for conducting fossil collection and detecting the termination of simulation. The triggering condition of GVT computation in typical approaches is generally based on the wall-clock time or logical time intervals. However, the GVT value depends on the timestamps of events rather than the wall-clock time or logical time intervals. Therefore, it is difficult for the existing approaches to select appropriate time intervals to compute the GVT value. In this study, we propose a scalable GVT estimation algorithm based on Lower Bound of Event-Bulk-Time, which triggers the computation of the GVT value according to the number of processed events. In order to calculate the number of transient messages, our algorithm employs Event-Bulk to record the messages sent and received by Logical Processes. To eliminate the performance bottleneck, we adopt an overlapping computation approach to distribute the workload of GVT computation to all worker-threads. We compare our algorithm with the fast asynchronous GVT algorithm using PHOLD benchmark on the shared memory machine. Experimental results indicate that our algorithm has a light overhead and shows higher speedup and accuracy of GVT computation than the fast asynchronous GVT algorithm.

Solving large instances of the quadratic cost of partition problem on dense graphs by data correcting algorithms

NARCIS (Netherlands)

Goldengorin, Boris; Vink, Marius de

1999-01-01

The Data-Correcting Algorithm (DCA) corrects the data of a hard problem instance in such a way that we obtain an instance of a well solvable special case. For a given prescribed accuracy of the solution, the DCA uses a branch and bound scheme to make sure that the solution of the corrected instance

Fast Branch & Bound algorithms for optimal feature selection

Czech Academy of Sciences Publication Activity Database

Somol, Petr; Pudil, Pavel; Kittler, J.

2004-01-01

Roč. 26, č. 7 (2004), s. 900-912 ISSN 0162-8828 R&D Projects: GA ČR GA402/02/1271; GA ČR GA402/03/1310; GA AV ČR KSK1019101 Institutional research plan: CEZ:AV0Z1075907 Keywords : subset search * feature selection * search tree Subject RIV: BD - Theory of Information Impact factor: 4.352, year: 2004

Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem

DEFF Research Database (Denmark)

Fukasawa, R.; Longo, H.; Lysgaard, Jens

2006-01-01

with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price...

Improved Monkey-King Genetic Algorithm for Solving Large Winner Determination in Combinatorial Auction

Science.gov (United States)

Li, Yuzhong

Using GA solve the winner determination problem (WDP) with large bids and items, run under different distribution, because the search space is large, constraint complex and it may easy to produce infeasible solution, would affect the efficiency and quality of algorithm. This paper present improved MKGA, including three operator: preprocessing, insert bid and exchange recombination, and use Monkey-king elite preservation strategy. Experimental results show that improved MKGA is better than SGA in population size and computation. The problem that traditional branch and bound algorithm hard to solve, improved MKGA can solve and achieve better effect.

Nonmyopic Sensor Scheduling and its Efficient Implementation for Target Tracking Applications

Directory of Open Access Journals (Sweden)

Morrell Darryl

2006-01-01

Full Text Available We propose two nonmyopic sensor scheduling algorithms for target tracking applications. We consider a scenario where a bearing-only sensor is constrained to move in a finite number of directions to track a target in a two-dimensional plane. Both algorithms provide the best sensor sequence by minimizing a predicted expected scheduler cost over a finite time-horizon. The first algorithm approximately computes the scheduler costs based on the predicted covariance matrix of the tracker error. The second algorithm uses the unscented transform in conjunction with a particle filter to approximate covariance-based costs or information-theoretic costs. We also propose the use of two branch-and-bound-based optimal pruning algorithms for efficient implementation of the scheduling algorithms. We design the first pruning algorithm by combining branch-and-bound with a breadth-first search and a greedy-search; the second pruning algorithm combines branch-and-bound with a uniform-cost search. Simulation results demonstrate the advantage of nonmyopic scheduling over myopic scheduling and the significant savings in computational and memory resources when using the pruning algorithms.

Dissociation of branched-chain alpha-keto acid dehydrogenase kinase (BDK) from branched-chain alpha-keto acid dehydrogenase complex (BCKDC) by BDK inhibitors.

Science.gov (United States)

Murakami, Taro; Matsuo, Masayuki; Shimizu, Ayako; Shimomura, Yoshiharu

2005-02-01

Branched-chain alpha-keto acid dehydrogenase kinase (BDK) phosphorylates and inactivates the branched-chain alpha-keto acid dehydrogenase complex (BCKDC), which is the rate-limiting enzyme in the branched-chain amino acid catabolism. BDK has been believed to be bound to the BCKDC. However, recent our studies demonstrated that protein-protein interaction between BDK and BCKDC is one of the factors to regulate BDK activity. Furthermore, only the bound form of BDK appears to have its activity. In the present study, we examined effects of BDK inhibitors on the amount of BDK bound to the BCKDC using rat liver extracts. The bound form of BDK in the extracts of liver from low protein diet-fed rats was measured by an immunoprecipitation pull down assay with or without BDK inhibitors. Among the BDK inhibitors. alpha-ketoisocaproate, alpha-chloroisocaproate, and a-ketoisovalerate released the BDK from the complex. Furthermore, the releasing effect of these inhibitors on the BDK appeared to depend on their inhibition constants. On the other hand, clofibric acid and thiamine pyrophosphate had no effect on the protein-protein interaction between two enzymes. These results suggest that the dissociation of the BDK from the BCKDC is one of the mechanisms responsible for the action of some inhibitors to BDK.

On the Optimization and Parallelizing Little Algorithm for Solving the Traveling Salesman Problem

Directory of Open Access Journals (Sweden)

V. V. Vasilchikov

2016-01-01

Full Text Available The paper describes some ways to accelerate solving the NP-complete Traveling Salesman Problem. The classic Little algorithm belonging to the category of ”branch and bound methods” can solve it both for directed and undirected graphs. However, for undirected graphs its operation can be accelerated by eliminating the consideration of branches examined earlier. The paper proposes changes to be made in the key operations of the algorithm to speed up its execution. It also describes the results of an experiment that demonstrated a significant acceleration of solving the problem by using an advanced algorithm. Another way to speed up the work is to parallelize the algorithm. For problems of this kind it is difficult to break the task into a sufficient number of subtasks having comparable complexity. Their parallelism arises dynamically during the execution. For such problems, it seems reasonable to use parallel-recursive algorithms. In our case the use of the library RPM ParLib developed by the author was a good choice. It allows us to develop effective applications for parallel computing on a local network using any .NET-compatible programming language. We used C# to develop the programs. Parallel applications were developed as for basic and modified algorithms, the comparing of their speed was made. Experiments were performed for the graphs with the number of vertexes up to 45 and with the number of network computers up to 16. We also investigated the acceleration that can be achieved by parallelizing the basic Little algorithm for directed graphs. The results of these experiments are also presented in the paper. 

Branch and bound algorithms to solve semiring constraint satisfaction problems

CSIR Research Space (South Africa)

Leenen, L

2008-12-01

Full Text Available The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. Considerable research has been done in solving SCSPs, but limited work has been done in building...

On а Recursive-Parallel Algorithm for Solving the Knapsack Problem

Directory of Open Access Journals (Sweden)

Vladimir V. Vasilchikov

2018-01-01

Full Text Available In this paper, we offer an efficient parallel algorithm for solving the NP-complete Knapsack Problem in its basic, so-called 0-1 variant. To find its exact solution, algorithms belonging to the category ”branch and bound methods” have long been used. To speed up the solving with varying degrees of efficiency, various options for parallelizing computations are also used. We propose here an algorithm for solving the problem, based on the paradigm of recursive-parallel computations. We consider it suited well for problems of this kind, when it is difficult to immediately break up the computations into a sufficient number of subtasks that are comparable in complexity, since they appear dynamically at run time. We used the RPM ParLib library, developed by the author, as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network in the .NET Framework. Such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support for the .NET Framework can be used as a programming language in conjunction with this library. For our experiments, we developed some C# applications using this library. The main purpose of these experiments was to study the acceleration achieved by recursive-parallel computing. A detailed description of the algorithm and its testing, as well as the results obtained, are also given in the paper.

Capacity Bounds for Parallel Optical Wireless Channels

KAUST Repository

Chaaban, Anas; Rezki, Zouheir; Alouini, Mohamed-Slim

2016-01-01

A system consisting of parallel optical wireless channels with a total average intensity constraint is studied. Capacity upper and lower bounds for this system are derived. Under perfect channel-state information at the transmitter (CSIT), the bounds have to be optimized with respect to the power allocation over the parallel channels. The optimization of the lower bound is non-convex, however, the KKT conditions can be used to find a list of possible solutions one of which is optimal. The optimal solution can then be found by an exhaustive search algorithm, which is computationally expensive. To overcome this, we propose low-complexity power allocation algorithms which are nearly optimal. The optimized capacity lower bound nearly coincides with the capacity at high SNR. Without CSIT, our capacity bounds lead to upper and lower bounds on the outage probability. The outage probability bounds meet at high SNR. The system with average and peak intensity constraints is also discussed.

Markov branching diffusions: martingales, Girsanov type theorems and applications to the long term behaviour

NARCIS (Netherlands)

Engländer, J.; Kyprianou, A.E.

2001-01-01

Consider a spatial branching particle process where the underlying motion is a conservative diffusion on D C Rd corresponding to the elliptic op- erator L on D, and the branching is strictly binary (dyadic), with spatially varying rate ß(x) => 0 (and ß <> 0) which is assumed to be bounded

Efficient Geo-Computational Algorithms for Constructing Space-Time Prisms in Road Networks

Directory of Open Access Journals (Sweden)

Hui-Ping Chen

2016-11-01

Full Text Available The Space-time prism (STP is a key concept in time geography for analyzing human activity-travel behavior under various Space-time constraints. Most existing time-geographic studies use a straightforward algorithm to construct STPs in road networks by using two one-to-all shortest path searches. However, this straightforward algorithm can introduce considerable computational overhead, given the fact that accessible links in a STP are generally a small portion of the whole network. To address this issue, an efficient geo-computational algorithm, called NTP-A*, is proposed. The proposed NTP-A* algorithm employs the A* and branch-and-bound techniques to discard inaccessible links during two shortest path searches, and thereby improves the STP construction performance. Comprehensive computational experiments are carried out to demonstrate the computational advantage of the proposed algorithm. Several implementation techniques, including the label-correcting technique and the hybrid link-node labeling technique, are discussed and analyzed. Experimental results show that the proposed NTP-A* algorithm can significantly improve STP construction performance in large-scale road networks by a factor of 100, compared with existing algorithms.

Solving binary-state multi-objective reliability redundancy allocation series-parallel problem using efficient epsilon-constraint, multi-start partial bound enumeration algorithm, and DEA

International Nuclear Information System (INIS)

Khalili-Damghani, Kaveh; Amiri, Maghsoud

2012-01-01

In this paper, a procedure based on efficient epsilon-constraint method and data envelopment analysis (DEA) is proposed for solving binary-state multi-objective reliability redundancy allocation series-parallel problem (MORAP). In first module, a set of qualified non-dominated solutions on Pareto front of binary-state MORAP is generated using an efficient epsilon-constraint method. In order to test the quality of generated non-dominated solutions in this module, a multi-start partial bound enumeration algorithm is also proposed for MORAP. The performance of both procedures is compared using different metrics on well-known benchmark instance. The statistical analysis represents that not only the proposed efficient epsilon-constraint method outperform the multi-start partial bound enumeration algorithm but also it improves the founded upper bound of benchmark instance. Then, in second module, a DEA model is supplied to prune the generated non-dominated solutions of efficient epsilon-constraint method. This helps reduction of non-dominated solutions in a systematic manner and eases the decision making process for practical implementations. - Highlights: ► A procedure based on efficient epsilon-constraint method and DEA was proposed for solving MORAP. ► The performance of proposed procedure was compared with a multi-start PBEA. ► Methods were statistically compared using multi-objective metrics.

Computing Bounds on Resource Levels for Flexible Plans

Science.gov (United States)

Muscvettola, Nicola; Rijsman, David

2009-01-01

A new algorithm efficiently computes the tightest exact bound on the levels of resources induced by a flexible activity plan (see figure). Tightness of bounds is extremely important for computations involved in planning because tight bounds can save potentially exponential amounts of search (through early backtracking and detection of solutions), relative to looser bounds. The bound computed by the new algorithm, denoted the resource-level envelope, constitutes the measure of maximum and minimum consumption of resources at any time for all fixed-time schedules in the flexible plan. At each time, the envelope guarantees that there are two fixed-time instantiations one that produces the minimum level and one that produces the maximum level. Therefore, the resource-level envelope is the tightest possible resource-level bound for a flexible plan because any tighter bound would exclude the contribution of at least one fixed-time schedule. If the resource- level envelope can be computed efficiently, one could substitute looser bounds that are currently used in the inner cores of constraint-posting scheduling algorithms, with the potential for great improvements in performance. What is needed to reduce the cost of computation is an algorithm, the measure of complexity of which is no greater than a low-degree polynomial in N (where N is the number of activities). The new algorithm satisfies this need. In this algorithm, the computation of resource-level envelopes is based on a novel combination of (1) the theory of shortest paths in the temporal-constraint network for the flexible plan and (2) the theory of maximum flows for a flow network derived from the temporal and resource constraints. The measure of asymptotic complexity of the algorithm is O(N O(maxflow(N)), where O(x) denotes an amount of computing time or a number of arithmetic operations proportional to a number of the order of x and O(maxflow(N)) is the measure of complexity (and thus of cost) of a maximumflow

State-set branching

DEFF Research Database (Denmark)

Jensen, Rune Møller; Veloso, Manuela M.; Bryant, Randal E.

2008-01-01

In this article, we present a framework called state-set branching that combines symbolic search based on reduced ordered Binary Decision Diagrams (BDDs) with best-first search, such as A* and greedy best-first search. The framework relies on an extension of these algorithms from expanding a sing...

MAXIMUM r-REGULAR INDUCED SUBGRAPH PROBLEM: FAST EXPONENTIAL ALGORITHMS AND COMBINATORIAL BOUNDS

DEFF Research Database (Denmark)

Gupta, S.; Raman, V.; Saurabh, S.

2012-01-01

We show that for a fixed r, the number of maximal r-regular induced subgraphs in any graph with n vertices is upper bounded by O(c(n)), where c is a positive constant strictly less than 2. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of 3(n/3) on the n...

Comparing branch-and-price algorithms for the Multi-Commodity k-splittable Maximum Flow Problem

DEFF Research Database (Denmark)

Gamst, Mette; Petersen, Bjørn

2012-01-01

-Protocol Label Switching. The problem has previously been solved to optimality through branch-and-price. In this paper we propose two exact solution methods both based on an alternative decomposition. The two methods differ in their branching strategy. The first method, which branches on forbidden edge sequences...

Circulation of Railway Rolling Stock: A Branch-and-Price Approach

NARCIS (Netherlands)

M. Peeters (Marc); L.G. Kroon (Leo)

2003-01-01

textabstractWe describe an algorithmic approach to determine an efficient railway rolling stock circulation on a single line or on a set of interacting lines. Given the timetable and the passengers? seat demand, we develop a branch-and-price algorithm that results in an allocation of rolling

The relationship between randomness and power-law distributed move lengths in random walk algorithms

Science.gov (United States)

Sakiyama, Tomoko; Gunji, Yukio-Pegio

2014-05-01

Recently, we proposed a new random walk algorithm, termed the REV algorithm, in which the agent alters the directional rule that governs it using the most recent four random numbers. Here, we examined how a non-bounded number, i.e., "randomness" regarding move direction, was important for optimal searching and power-law distributed step lengths in rule change. We proposed two algorithms: the REV and REV-bounded algorithms. In the REV algorithm, one of the four random numbers used to change the rule is non-bounded. In contrast, all four random numbers in the REV-bounded algorithm are bounded. We showed that the REV algorithm exhibited more consistent power-law distributed step lengths and flexible searching behavior.

A fast algorithm for determining bounds and accurate approximate p-values of the rank product statistic for replicate experiments.

Science.gov (United States)

Heskes, Tom; Eisinga, Rob; Breitling, Rainer

2014-11-21

The rank product method is a powerful statistical technique for identifying differentially expressed molecules in replicated experiments. A critical issue in molecule selection is accurate calculation of the p-value of the rank product statistic to adequately address multiple testing. Both exact calculation and permutation and gamma approximations have been proposed to determine molecule-level significance. These current approaches have serious drawbacks as they are either computationally burdensome or provide inaccurate estimates in the tail of the p-value distribution. We derive strict lower and upper bounds to the exact p-value along with an accurate approximation that can be used to assess the significance of the rank product statistic in a computationally fast manner. The bounds and the proposed approximation are shown to provide far better accuracy over existing approximate methods in determining tail probabilities, with the slightly conservative upper bound protecting against false positives. We illustrate the proposed method in the context of a recently published analysis on transcriptomic profiling performed in blood. We provide a method to determine upper bounds and accurate approximate p-values of the rank product statistic. The proposed algorithm provides an order of magnitude increase in throughput as compared with current approaches and offers the opportunity to explore new application domains with even larger multiple testing issue. The R code is published in one of the Additional files and is available at http://www.ru.nl/publish/pages/726696/rankprodbounds.zip .

F-Theory, spinning black holes and multi-string branches

International Nuclear Information System (INIS)

Haghighat, Babak; Murthy, Sameer; Vafa, Cumrun; Vandoren, Stefan

2016-01-01

We study 5d supersymmetric black holes which descend from strings of generic N=(1,0) supergravity in 6d. These strings have an F-theory realization in 6d as D3 branes wrapping smooth genus g curves in the base of elliptic 3-folds. They enjoy (0,4) worldsheet supersymmetry with an extra SU(2) L current algebra at level g realized on the left-movers. When the smooth curves degenerate they lead to multi-string branches and we find that the microscopic worldsheet theory flows in the IR to disconnected 2d CFTs having different central charges. The single string sector is the one with maximal central charge, which when wrapped on a circle, leads to a 5d spinning BPS black hole whose horizon volume agrees with the leading entropy prediction from the Cardy formula. However, we find new phenomena where this branch meets other branches of the CFT. These include multi-string configurations which have no bound states in 6 dimensions but are bound through KK momenta when wrapping a circle, as well as loci where the curves degenerate to spheres. These loci lead to black hole configurations which can have total angular momentum relative to a Taub-Nut center satisfying J 2 >M 3 and whose number of states, though exponentially large, grows much slower than those of the large spinning black hole.

Exponential Lower Bounds For Policy Iteration

OpenAIRE

Fearnley, John

2010-01-01

We study policy iteration for infinite-horizon Markov decision processes. It has recently been shown policy iteration style algorithms have exponential lower bounds in a two player game setting. We extend these lower bounds to Markov decision processes with the total reward and average-reward optimality criteria.

Sharp Bounds by Probability-Generating Functions and Variable Drift

DEFF Research Database (Denmark)

Doerr, Benjamin; Fouz, Mahmoud; Witt, Carsten

2011-01-01

We introduce to the runtime analysis of evolutionary algorithms two powerful techniques: probability-generating functions and variable drift analysis. They are shown to provide a clean framework for proving sharp upper and lower bounds. As an application, we improve the results by Doerr et al....... (GECCO 2010) in several respects. First, the upper bound on the expected running time of the most successful quasirandom evolutionary algorithm for the OneMax function is improved from 1.28nln n to 0.982nlnn, which breaks the barrier of nln n posed by coupon-collector processes. Compared to the classical...

New Approaches for Very Large-Scale Integer Programming

Science.gov (United States)

2016-06-24

DISTRIBUTION/ AVAILABILITY STATEMENT Approved for Public Release 13. SUPPLEMENTARY NOTES 14. ABSTRACT The focus of this project is new computational... heuristics for integer programs in order to rapidly improve dual bounds. 2. Choosing good branching variables in branch-and-bound algorithms for MIP. 3...programming, algorithms, parallel processing, machine learning, heuristics 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF ABSTRACT UU 18. NUMBER OF

Effect of a culture-based screening algorithm on tuberculosis incidence in immigrants and refugees bound for the United States: a population-based cross-sectional study.

Science.gov (United States)

Liu, Yecai; Posey, Drew L; Cetron, Martin S; Painter, John A

2015-03-17

Before 2007, immigrants and refugees bound for the United States were screened for tuberculosis (TB) by a smear-based algorithm that could not diagnose smear-negative/culture-positive TB. In 2007, the Centers for Disease Control and Prevention implemented a culture-based algorithm. To evaluate the effect of the culture-based algorithm on preventing the importation of TB to the United States by immigrants and refugees from foreign countries. Population-based, cross-sectional study. Panel physician sites for overseas medical examination. Immigrants and refugees with TB. Comparison of the increase of smear-negative/culture-positive TB cases diagnosed overseas among immigrants and refugees by the culture-based algorithm with the decline of reported cases among foreign-born persons within 1 year after arrival in the United States from 2007 to 2012. Of the 3 212 421 arrivals of immigrants and refugees from 2007 to 2012, a total of 1 650 961 (51.4%) were screened by the smear-based algorithm and 1 561 460 (48.6%) were screened by the culture-based algorithm. Among the 4032 TB cases diagnosed by the culture-based algorithm, 2195 (54.4%) were smear-negative/culture-positive. Before implementation (2002 to 2006), the annual number of reported cases among foreign-born persons within 1 year after arrival was relatively constant (range, 1424 to 1626 cases; mean, 1504 cases) but decreased from 1511 to 940 cases during implementation (2007 to 2012). During the same period, the annual number of smear-negative/culture-positive TB cases diagnosed overseas among immigrants and refugees bound for the United States by the culture-based algorithm increased from 4 to 629. This analysis did not control for the decline in new arrivals of nonimmigrant visitors to the United States and the decrease of incidence of TB in their countries of origin. Implementation of the culture-based algorithm may have substantially reduced the incidence of TB among newly arrived, foreign-born persons in

The hyperbolic step potential: Anti-bound states, SUSY partners and Wigner time delays

Energy Technology Data Exchange (ETDEWEB)

Gadella, M. [Departamento de Física Teórica, Atómica y Óptica and IMUVA, Universidad de Valladolid, E-47011 Valladolid (Spain); Kuru, Ş. [Department of Physics, Faculty of Science, Ankara University, 06100 Ankara (Turkey); Negro, J., E-mail: jnegro@fta.uva.es [Departamento de Física Teórica, Atómica y Óptica and IMUVA, Universidad de Valladolid, E-47011 Valladolid (Spain)

2017-04-15

We study the scattering produced by a one dimensional hyperbolic step potential, which is exactly solvable and shows an unusual interest because of its asymmetric character. The analytic continuation of the scattering matrix in the momentum representation has a branch cut and an infinite number of simple poles on the negative imaginary axis which are related with the so called anti-bound states. This model does not show resonances. Using the wave functions of the anti-bound states, we obtain supersymmetric (SUSY) partners which are the series of Rosen–Morse II potentials. We have computed the Wigner reflection and transmission time delays for the hyperbolic step and such SUSY partners. Our results show that the more bound states a partner Hamiltonian has the smaller is the time delay. We also have evaluated time delays for the hyperbolic step potential in the classical case and have obtained striking similitudes with the quantum case. - Highlights: • The scattering matrix of hyperbolic step potential is studied. • The scattering matrix has a branch cut and an infinite number of poles. • The poles are associated to anti-bound states. • Susy partners using antibound states are computed. • Wigner time delays for the hyperbolic step and partner potentials are compared.

The influence of branch order on optimal leaf vein geometries: Murray's law and area preserving branching.

Directory of Open Access Journals (Sweden)

Charles A Price

Full Text Available Models that predict the form of hierarchical branching networks typically invoke optimization based on biomechanical similitude, the minimization of impedance to fluid flow, or construction costs. Unfortunately, due to the small size and high number of vein segments found in real biological networks, complete descriptions of networks needed to evaluate such models are rare. To help address this we report results from the analysis of the branching geometry of 349 leaf vein networks comprising over 1.5 million individual vein segments. In addition to measuring the diameters of individual veins before and after vein bifurcations, we also assign vein orders using the Horton-Strahler ordering algorithm adopted from the study of river networks. Our results demonstrate that across all leaves, both radius tapering and the ratio of daughter to parent branch areas for leaf veins are in strong agreement with the expectation from Murray's law. However, as veins become larger, area ratios shift systematically toward values expected under area-preserving branching. Our work supports the idea that leaf vein networks differentiate roles of leaf support and hydraulic supply between hierarchical orders.

Combining Alphas via Bounded Regression

Directory of Open Access Journals (Sweden)

Zura Kakushadze

2015-11-01

Full Text Available We give an explicit algorithm and source code for combining alpha streams via bounded regression. In practical applications, typically, there is insufficient history to compute a sample covariance matrix (SCM for a large number of alphas. To compute alpha allocation weights, one then resorts to (weighted regression over SCM principal components. Regression often produces alpha weights with insufficient diversification and/or skewed distribution against, e.g., turnover. This can be rectified by imposing bounds on alpha weights within the regression procedure. Bounded regression can also be applied to stock and other asset portfolio construction. We discuss illustrative examples.

Runway Operations Planning: A Two-Stage Heuristic Algorithm

Science.gov (United States)

Anagnostakis, Ioannis; Clarke, John-Paul

2003-01-01

The airport runway is a scarce resource that must be shared by different runway operations (arrivals, departures and runway crossings). Given the possible sequences of runway events, careful Runway Operations Planning (ROP) is required if runway utilization is to be maximized. From the perspective of departures, ROP solutions are aircraft departure schedules developed by optimally allocating runway time for departures given the time required for arrivals and crossings. In addition to the obvious objective of maximizing throughput, other objectives, such as guaranteeing fairness and minimizing environmental impact, can also be incorporated into the ROP solution subject to constraints introduced by Air Traffic Control (ATC) procedures. This paper introduces a two stage heuristic algorithm for solving the Runway Operations Planning (ROP) problem. In the first stage, sequences of departure class slots and runway crossings slots are generated and ranked based on departure runway throughput under stochastic conditions. In the second stage, the departure class slots are populated with specific flights from the pool of available aircraft, by solving an integer program with a Branch & Bound algorithm implementation. Preliminary results from this implementation of the two-stage algorithm on real-world traffic data are presented.

Maximum error-bounded Piecewise Linear Representation for online stream approximation

KAUST Repository

Xie, Qing; Pang, Chaoyi; Zhou, Xiaofang; Zhang, Xiangliang; Deng, Ke

2014-01-01

Given a time series data stream, the generation of error-bounded Piecewise Linear Representation (error-bounded PLR) is to construct a number of consecutive line segments to approximate the stream, such that the approximation error does not exceed a prescribed error bound. In this work, we consider the error bound in L∞ norm as approximation criterion, which constrains the approximation error on each corresponding data point, and aim on designing algorithms to generate the minimal number of segments. In the literature, the optimal approximation algorithms are effectively designed based on transformed space other than time-value space, while desirable optimal solutions based on original time domain (i.e., time-value space) are still lacked. In this article, we proposed two linear-time algorithms to construct error-bounded PLR for data stream based on time domain, which are named OptimalPLR and GreedyPLR, respectively. The OptimalPLR is an optimal algorithm that generates minimal number of line segments for the stream approximation, and the GreedyPLR is an alternative solution for the requirements of high efficiency and resource-constrained environment. In order to evaluate the superiority of OptimalPLR, we theoretically analyzed and compared OptimalPLR with the state-of-art optimal solution in transformed space, which also achieves linear complexity. We successfully proved the theoretical equivalence between time-value space and such transformed space, and also discovered the superiority of OptimalPLR on processing efficiency in practice. The extensive results of empirical evaluation support and demonstrate the effectiveness and efficiency of our proposed algorithms.

Maximum error-bounded Piecewise Linear Representation for online stream approximation

KAUST Repository

Xie, Qing

2014-04-04

Given a time series data stream, the generation of error-bounded Piecewise Linear Representation (error-bounded PLR) is to construct a number of consecutive line segments to approximate the stream, such that the approximation error does not exceed a prescribed error bound. In this work, we consider the error bound in L∞ norm as approximation criterion, which constrains the approximation error on each corresponding data point, and aim on designing algorithms to generate the minimal number of segments. In the literature, the optimal approximation algorithms are effectively designed based on transformed space other than time-value space, while desirable optimal solutions based on original time domain (i.e., time-value space) are still lacked. In this article, we proposed two linear-time algorithms to construct error-bounded PLR for data stream based on time domain, which are named OptimalPLR and GreedyPLR, respectively. The OptimalPLR is an optimal algorithm that generates minimal number of line segments for the stream approximation, and the GreedyPLR is an alternative solution for the requirements of high efficiency and resource-constrained environment. In order to evaluate the superiority of OptimalPLR, we theoretically analyzed and compared OptimalPLR with the state-of-art optimal solution in transformed space, which also achieves linear complexity. We successfully proved the theoretical equivalence between time-value space and such transformed space, and also discovered the superiority of OptimalPLR on processing efficiency in practice. The extensive results of empirical evaluation support and demonstrate the effectiveness and efficiency of our proposed algorithms.

Semi-inclusive B->K(K*)X decays with initial bound state effects

International Nuclear Information System (INIS)

He, Xiao-Gang; Jin, Changhao; Ma, J. P.

2001-01-01

The effects of the initial b quark bound state for the semi-inclusive decays B->K(K * )X are studied using light cone expansion and heavy quark effective theory methods. We find that the initial bound state effects on the branching ratios and CP asymmetries are small. In the light cone expansion approach, the CP-averaged branching ratios are increased by about 2% with respect to the free b-quark decay. For {bar B} 0 ->K - (K *- )X, the CP-averaged branching ratios are sensitive to the phase γ and the CP asymmetry can be as large as 7% (14%), whereas for B - ->{bar K} 0 ({bar K} *0 )X the CP-averaged branching ratios are not sensitive to γ and the CP asymmetries are small ( -4 [(0.25 - 2.0)x10 -4 ] for {bar B} 0 ->K - (K *- )X and (0.77 - 0.84)x10 -4 [(0.67 - 0.74)x10 -4 ] for B - ->{bar K} 0 ({bar K} *0 )X, depending on the value of the CP violating phase γ. In the heavy quark effective theory approach, we find that the branching ratios are decreased by about 10% and the CP asymmetries are not affected. These predictions can be tested in the near future

Trial and Error: A new Approach to Space-Bounded Learning

DEFF Research Database (Denmark)

Ameur, F.; Fischer, Paul; Hoeffgen, H.-U.

1996-01-01

A pac-learning algorithm is d-space bounded, if it stores at most d examples from the sample at any time. We characterize the d-space learnable concept classes. For this purpose we introduce the compression parameter of a concept class 𝒞 and design our trial and error learning algorithm. We ...

Capacity bounds for parallel IM-DD optical wireless channels

KAUST Repository

Chaaban, Anas; Rezki, Zouheir; Alouini, Mohamed-Slim

2016-01-01

A system consisting of parallel intensity-modulation direct-detection optical wireless channels with a total average intensity constraint is studied. Capacity upper and lower bounds for this system are derived. If channel-state information is available at the transmitter, the bounds have to be optimized with respect to intensity allocation over the parallel channels. The optimization of the lower bound is non-convex, however, the Karush-Kuhn-Tucker conditions can be used to find a list of possible solutions one of which is optimal. The optimal solution can then be found by an exhaustive search algorithm, which is computationally expensive. To overcome this, we propose a low-complexity intensity allocation algorithm which is nearly optimal. The optimized capacity lower bound coincides with the capacity at high signal-to-noise ratio. © 2016 IEEE.

Capacity bounds for parallel IM-DD optical wireless channels

KAUST Repository

Chaaban, Anas

2016-07-26

A system consisting of parallel intensity-modulation direct-detection optical wireless channels with a total average intensity constraint is studied. Capacity upper and lower bounds for this system are derived. If channel-state information is available at the transmitter, the bounds have to be optimized with respect to intensity allocation over the parallel channels. The optimization of the lower bound is non-convex, however, the Karush-Kuhn-Tucker conditions can be used to find a list of possible solutions one of which is optimal. The optimal solution can then be found by an exhaustive search algorithm, which is computationally expensive. To overcome this, we propose a low-complexity intensity allocation algorithm which is nearly optimal. The optimized capacity lower bound coincides with the capacity at high signal-to-noise ratio. © 2016 IEEE.

Optimal Bounds in Parametric LTL Games

Directory of Open Access Journals (Sweden)

Martin Zimmermann

2011-06-01

Full Text Available We consider graph games of infinite duration with winning conditions in parameterized linear temporal logic, where the temporal operators are equipped with variables for time bounds. In model checking such specifications were introduced as "PLTL" by Alur et al. and (in a different version called "PROMPT-LTL" by Kupferman et al.. We present an algorithm to determine optimal variable valuations that allow a player to win a game. Furthermore, we show how to determine whether a player wins a game with respect to some, infinitely many, or all valuations. All our algorithms run in doubly-exponential time; so, adding bounded temporal operators does not increase the complexity compared to solving plain LTL games.

Bounded-Angle Iterative Decoding of LDPC Codes

Science.gov (United States)

Dolinar, Samuel; Andrews, Kenneth; Pollara, Fabrizio; Divsalar, Dariush

2009-01-01

Bounded-angle iterative decoding is a modified version of conventional iterative decoding, conceived as a means of reducing undetected-error rates for short low-density parity-check (LDPC) codes. For a given code, bounded-angle iterative decoding can be implemented by means of a simple modification of the decoder algorithm, without redesigning the code. Bounded-angle iterative decoding is based on a representation of received words and code words as vectors in an n-dimensional Euclidean space (where n is an integer).

NeatSort - A practical adaptive algorithm

OpenAIRE

La Rocca, Marcello; Cantone, Domenico

2014-01-01

We present a new adaptive sorting algorithm which is optimal for most disorder metrics and, more important, has a simple and quick implementation. On input $X$, our algorithm has a theoretical $\\Omega (|X|)$ lower bound and a $\\mathcal{O}(|X|\\log|X|)$ upper bound, exhibiting amazing adaptive properties which makes it run closer to its lower bound as disorder (computed on different metrics) diminishes. From a practical point of view, \\textit{NeatSort} has proven itself competitive with (and of...

A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes

DEFF Research Database (Denmark)

Masson, Renaud; Røpke, Stefan; Lehuédé, Fabien

2014-01-01

for the PDPS and a branch-and-cut-and-price algorithm to solve it. The pricing sub-problem, an Elementary Shortest Path Problem with Resource Constraints (ESPPRC), is solved with a labeling algorithm enhanced with efficient dominance rules. Three families of valid inequalities are used to strengthen...

THREE-DIMENSIONAL RECONSTRUCTION OF THE VIRTUAL PLANT BRANCHING STRUCTURE BASED ON TERRESTRIAL LIDAR TECHNOLOGIES AND L-SYSTEM

Directory of Open Access Journals (Sweden)

Y. Gong

2018-04-01

Full Text Available For the purpose of extracting productions of some specific branching plants effectively and realizing its 3D reconstruction, Terrestrial LiDAR data was used as extraction source of production, and a 3D reconstruction method based on Terrestrial LiDAR technologies combined with the L-system was proposed in this article. The topology structure of the plant architectures was extracted using the point cloud data of the target plant with space level segmentation mechanism. Subsequently, L-system productions were obtained and the structural parameters and production rules of branches, which fit the given plant, was generated. A three-dimensional simulation model of target plant was established combined with computer visualization algorithm finally. The results suggest that the method can effectively extract a given branching plant topology and describes its production, realizing the extraction of topology structure by the computer algorithm for given branching plant and also simplifying the extraction of branching plant productions which would be complex and time-consuming by L-system. It improves the degree of automation in the L-system extraction of productions of specific branching plants, providing a new way for the extraction of branching plant production rules.

Three-Dimensional Reconstruction of the Virtual Plant Branching Structure Based on Terrestrial LIDAR Technologies and L-System

Science.gov (United States)

Gong, Y.; Yang, Y.; Yang, X.

2018-04-01

For the purpose of extracting productions of some specific branching plants effectively and realizing its 3D reconstruction, Terrestrial LiDAR data was used as extraction source of production, and a 3D reconstruction method based on Terrestrial LiDAR technologies combined with the L-system was proposed in this article. The topology structure of the plant architectures was extracted using the point cloud data of the target plant with space level segmentation mechanism. Subsequently, L-system productions were obtained and the structural parameters and production rules of branches, which fit the given plant, was generated. A three-dimensional simulation model of target plant was established combined with computer visualization algorithm finally. The results suggest that the method can effectively extract a given branching plant topology and describes its production, realizing the extraction of topology structure by the computer algorithm for given branching plant and also simplifying the extraction of branching plant productions which would be complex and time-consuming by L-system. It improves the degree of automation in the L-system extraction of productions of specific branching plants, providing a new way for the extraction of branching plant production rules.

Design of Hierarchical Ring Networks Using Branch-and-Price

DEFF Research Database (Denmark)

Thomadsen, Tommy; Stidsen, Thomas K.

2004-01-01

-ring is designed connecting the metro-rings, minimizing fixed link establishment costs of the federal-ring. A branch-and-price algorithm is presented for the design of the bottom layer and it is suggested that existing methods are used for the design of the federal-ring. Computational results are given...

A database of linear codes over F_13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm

Directory of Open Access Journals (Sweden)

Eric Z. Chen

2015-01-01

Full Text Available Error control codes have been widely used in data communications and storage systems. One central problem in coding theory is to optimize the parameters of a linear code and construct codes with best possible parameters. There are tables of best-known linear codes over finite fields of sizes up to 9. Recently, there has been a growing interest in codes over $\\mathbb{F}_{13}$ and other fields of size greater than 9. The main purpose of this work is to present a database of best-known linear codes over the field $\\mathbb{F}_{13}$ together with upper bounds on the minimum distances. To find good linear codes to establish lower bounds on minimum distances, an iterative heuristic computer search algorithm is employed to construct quasi-twisted (QT codes over the field $\\mathbb{F}_{13}$ with high minimum distances. A large number of new linear codes have been found, improving previously best-known results. Tables of $[pm, m]$ QT codes over $\\mathbb{F}_{13}$ with best-known minimum distances as well as a table of lower and upper bounds on the minimum distances for linear codes of length up to 150 and dimension up to 6 are presented.

Reconstructing 3D Tree Models Using Motion Capture and Particle Flow

Directory of Open Access Journals (Sweden)

Jie Long

2013-01-01

Full Text Available Recovering tree shape from motion capture data is a first step toward efficient and accurate animation of trees in wind using motion capture data. Existing algorithms for generating models of tree branching structures for image synthesis in computer graphics are not adapted to the unique data set provided by motion capture. We present a method for tree shape reconstruction using particle flow on input data obtained from a passive optical motion capture system. Initial branch tip positions are estimated from averaged and smoothed motion capture data. Branch tips, as particles, are also generated within a bounding space defined by a stack of bounding boxes or a convex hull. The particle flow, starting at branch tips within the bounding volume under forces, creates tree branches. The forces are composed of gravity, internal force, and external force. The resulting shapes are realistic and similar to the original tree crown shape. Several tunable parameters provide control over branch shape and arrangement.

Greedy algorithms withweights for construction of partial association rules

KAUST Repository

Moshkov, Mikhail; Piliszczu, Marcin; Zielosko, Beata Marta

2009-01-01

This paper is devoted to the study of approximate algorithms for minimization of the total weight of attributes occurring in partial association rules. We consider mainly greedy algorithms with weights for construction of rules. The paper contains bounds on precision of these algorithms and bounds on the minimal weight of partial association rules based on an information obtained during the greedy algorithm run.

Greedy algorithms withweights for construction of partial association rules

KAUST Repository

Moshkov, Mikhail

2009-09-10

This paper is devoted to the study of approximate algorithms for minimization of the total weight of attributes occurring in partial association rules. We consider mainly greedy algorithms with weights for construction of rules. The paper contains bounds on precision of these algorithms and bounds on the minimal weight of partial association rules based on an information obtained during the greedy algorithm run.

Solving the simple plant location problem using a data correcting approach

NARCIS (Netherlands)

Goldengorin, Boris

2001-01-01

The Data Correcting Algorithm is a branch and bound algorithm in which thedata of a given problem instance is ‘corrected’ at each branching in such a waythat the new instance will be as close as possible to a polynomially solvableinstance and the result satisfies an acceptable accuracy (the

Partial Evaluation of the Euclidian Algorithm

DEFF Research Database (Denmark)

Danvy, Olivier; Goldberg, Mayer

1997-01-01

-like behavior. Each of them presents a challenge for partial evaluation. The Euclidian algorithm is one of them, and in this article, we make it amenable to partial evaluation. We observe that the number of iterations in the Euclidian algorithm is bounded by a number that can be computed given either of the two...... arguments. We thus rephrase this algorithm using bounded recursion. The resulting program is better suited for automatic unfolding and thus for partial evaluation. Its specialization is efficient....

Energy-bounded caging: Formal definition and 2-D energy lower bound algorithm based on weighted alpha shapes

NARCIS (Netherlands)

Mahler, Jeffrey; Pokorny, Florian T.; McCarthy, Zoe; van der Stappen, A.F.; Goldberg, Ken

Caging grasps are valuable as they can be robust to bounded variations in object shape and pose, do not depend on friction, and enable transport of an object without full immobilization. Complete caging of an object is useful but may not be necessary in cases where forces such as gravity are

Convergence in gradient systems with branching of equilibria

International Nuclear Information System (INIS)

Galaktionov, V A; Pohozaev, Stanislav I; Shishkov, A E

2007-01-01

The basic model is a semilinear elliptic equation with coercive C 1 non-linearity: Δψ+f(ψ)=0 in Ω, ψ=0 on ∂Ω, where Ω subset of R N is a bounded smooth domain. The main hypothesis (H R ) about resonance branching is as follows: if a branching of equilibria occurs at a point ψ with k-dimensional kernel of the linearized operator Δ+f'(ψ)I, then the branching subset S k at ψ is a locally smooth k-dimensional manifold. For N=1 the first result on the stabilization to a single equilibrium is due to Zelenyak (1968). It is shown that Zelenyak's approach, which is based on the analysis of Lyapunov functions, can be extended to general gradient systems in Hilbert spaces with smooth resonance branching. The case of asymptotically small non-autonomous perturbations of such systems is also considered. The approach developed here represents an alternative to Hale's stabilization method (1992) and other similar techniques in the theory of gradient systems. Bibliography: 32 titles.

Hitting times of local and global optima in genetic algorithms with very high selection pressure

Directory of Open Access Journals (Sweden)

Eremeev Anton V.

2017-01-01

Full Text Available The paper is devoted to upper bounds on the expected first hitting times of the sets of local or global optima for non-elitist genetic algorithms with very high selection pressure. The results of this paper extend the range of situations where the upper bounds on the expected runtime are known for genetic algorithms and apply, in particular, to the Canonical Genetic Algorithm. The obtained bounds do not require the probability of fitness-decreasing mutation to be bounded by a constant which is less than one.

Regularization by Functions of Bounded Variation and Applications to Image Enhancement

International Nuclear Information System (INIS)

Casas, E.; Kunisch, K.; Pola, C.

1999-01-01

Optimization problems regularized by bounded variation seminorms are analyzed. The optimality system is obtained and finite-dimensional approximations of bounded variation function spaces as well as of the optimization problems are studied. It is demonstrated that the choice of the vector norm in the definition of the bounded variation seminorm is of special importance for approximating subspaces consisting of piecewise constant functions. Algorithms based on a primal-dual framework that exploit the structure of these nondifferentiable optimization problems are proposed. Numerical examples are given for denoising of blocky images with very high noise

A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills

NARCIS (Netherlands)

Firat, M.; Briskorn, D.; Laugier, A.

2016-01-01

This paper deals with assigning hierarchically skilled technicians to jobs by considering preferences. We investigate stability definitions in multi-skill workforce assignments stemming from the notion of blocking pairs as stated in the Marriage model of Gale–Shapley. We propose a Branch-and-Price

Lower Bounds and Semi On-line Multiprocessor Scheduling

Directory of Open Access Journals (Sweden)

T.C. Edwin Cheng

2003-10-01

Full Text Available We are given a set of identical machines and a sequence of jobs from which we know the sum of the job weights in advance. The jobs have to be assigned on-line to one of the machines and the objective is to minimize the makespan. An algorithm with performance ratio 1.6 and a lower bound of 1.5 is presented. This improves recent results by Azar and Regev who published an algorithm with performance ratio 1.625 for the less general problem that the optimal makespan is known in advance.

Toward a minimum branching fraction for dark matter annihilation into electromagnetic final states

International Nuclear Information System (INIS)

Dent, James B.; Scherrer, Robert J.; Weiler, Thomas J.

2008-01-01

Observational limits on the high-energy neutrino background have been used to place general constraints on dark matter that annihilates only into standard model particles. Dark matter particles that annihilate into neutrinos will also inevitably branch into electromagnetic final states through higher-order tree and loop diagrams that give rise to charged leptons, and these charged particles can transfer their energy into photons via synchrotron radiation or inverse Compton scattering. In the context of effective field theory, we calculate the loop-induced branching ratio to charged leptons and show that it is generally quite large, typically > or approx. 1%, when the scale of the dark matter mass exceeds the electroweak scale, M W . For a branching fraction >or approx. 3%, the synchrotron radiation bounds on dark matter annihilation are currently stronger than the corresponding neutrino bounds in the interesting mass range from 100 GeV to 1 TeV. For dark matter masses below M W , our work provides a plausible framework for the construction of a model for 'neutrinos-only' dark matter annihilations.

On Leak Localization in the Main Branched and Simple Inclined Gas Pipelines

OpenAIRE

T. Davitashvili; G. Gubelidze

2013-01-01

In this paper two mathematical models for definition of gas accidental escape localization in the gas pipelines are suggested. The first model was created for leak localization in the horizontal branched pipeline and second one for leak detection in inclined section of the main gas pipeline. The algorithm of leak localization in the branched pipeline did not demand on knowledge of corresponding initial hydraulic parameters at entrance and ending points of each sections of pipeline. For detect...

A Model-Free No-arbitrage Price Bound for Variance Options

Energy Technology Data Exchange (ETDEWEB)

Bonnans, J. Frederic, E-mail: frederic.bonnans@inria.fr [Ecole Polytechnique, INRIA-Saclay (France); Tan Xiaolu, E-mail: xiaolu.tan@polytechnique.edu [Ecole Polytechnique, CMAP (France)

2013-08-01

We suggest a numerical approximation for an optimization problem, motivated by its applications in finance to find the model-free no-arbitrage bound of variance options given the marginal distributions of the underlying asset. A first approximation restricts the computation to a bounded domain. Then we propose a gradient projection algorithm together with the finite difference scheme to solve the optimization problem. We prove the general convergence, and derive some convergence rate estimates. Finally, we give some numerical examples to test the efficiency of the algorithm.

A new algorithm for the integration of exponential and logarithmic functions

Science.gov (United States)

Rothstein, M.

1977-01-01

An algorithm for symbolic integration of functions built up from the rational functions by repeatedly applying either the exponential or logarithm functions is discussed. This algorithm does not require polynomial factorization nor partial fraction decomposition and requires solutions of linear systems with only a small number of unknowns. It is proven that if this algorithm is applied to rational functions over the integers, a computing time bound for the algorithm can be obtained which is a polynomial in a bound on the integer length of the coefficients, and in the degrees of the numerator and denominator of the rational function involved.

Behavioral Consistency of C and Verilog Programs Using Bounded Model Checking

National Research Council Canada - National Science Library

Clarke, Edmund; Kroening, Daniel; Yorav, Karen

2003-01-01

.... We describe experimental results on various reactive present an algorithm that checks behavioral consistency between an ANSI-C program and a circuit given in Verilog using Bounded Model Checking...

Detection of Bundle Branch Block using Adaptive Bacterial Foraging Optimization and Neural Network

Directory of Open Access Journals (Sweden)

Padmavthi Kora

2017-03-01

Full Text Available The medical practitioners analyze the electrical activity of the human heart so as to predict various ailments by studying the data collected from the Electrocardiogram (ECG. A Bundle Branch Block (BBB is a type of heart disease which occurs when there is an obstruction along the pathway of an electrical impulse. This abnormality makes the heart beat irregular as there is an obstruction in the branches of heart, this results in pulses to travel slower than the usual. Our current study involved is to diagnose this heart problem using Adaptive Bacterial Foraging Optimization (ABFO Algorithm. The Data collected from MIT/BIH arrhythmia BBB database applied to an ABFO Algorithm for obtaining best(important feature from each ECG beat. These features later fed to Levenberg Marquardt Neural Network (LMNN based classifier. The results show the proposed classification using ABFO is better than some recent algorithms reported in the literature.

Solving the simple plant location problem using a data correcting approach

NARCIS (Netherlands)

Goldengorin, B.; Tijssen, G.A.; Ghosh, D.; Sierksma, G.

The Data Correcting Algorithm is a branch and bound type algorithm in which the data of a given problem instance is `corrected' at each branching in such a way that the new instance will be as close as possible to a polynomially solvable instance and the result satisfies an acceptable accuracy (the

Semi-automated tabulation of the 3D topology and morphology of branching networks using CT: application to the airway tree

International Nuclear Information System (INIS)

Sauret, V.; Bailey, A.G.

1999-01-01

Detailed information on biological branching networks (optical nerves, airways or blood vessels) is often required to improve the analysis of 3D medical imaging data. A semi-automated algorithm has been developed to obtain the full 3D topology and dimensions (direction cosine, length, diameter, branching and gravity angles) of branching networks using their CT images. It has been tested using CT images of a simple Perspex branching network and applied to the CT images of a human cast of the airway tree. The morphology and topology of the computer derived network were compared with the manually measured dimensions. Good agreement was found. The airways dimensions also compared well with previous values quoted in literature. This algorithm can provide complete data set analysis much more quickly than manual measurements. Its use is limited by the CT resolution which means that very small branches are not visible. New data are presented on the branching angles of the airway tree. (author)

A linear programming approach to characterizing norm bounded uncertainty from experimental data

Science.gov (United States)

Scheid, R. E.; Bayard, D. S.; Yam, Y.

1991-01-01

The linear programming spectral overbounding and factorization (LPSOF) algorithm, an algorithm for finding a minimum phase transfer function of specified order whose magnitude tightly overbounds a specified nonparametric function of frequency, is introduced. This method has direct application to transforming nonparametric uncertainty bounds (available from system identification experiments) into parametric representations required for modern robust control design software (i.e., a minimum-phase transfer function multiplied by a norm-bounded perturbation).

Branching ratio and angular distribution of ejected electrons from Eu 4f76p1/2 n d auto-ionizing states

International Nuclear Information System (INIS)

Wu Xiao-Rui; Shen Li; Zhang Kai; Dai Chang-Jian; Yang Yu-Na

2016-01-01

The branching ratios of ions and the angular distributions of electrons ejected from the Eu 4f 7 6p 1/2 n d auto-ionizing states are investigated with the velocity-map-imaging technique. To populate the above auto-ionizing states, the relevant bound Rydberg states have to be detected first. Two new bound Rydberg states are identified in the region between 41150 cm −1 and 44580 cm −1 , from which auto-ionization spectra of the Eu 4f 7 6p 1/2 n d states are observed with isolated core excitation method. With all preparations above, the branching ratios from the above auto-ionizing states to different final ionic states and the angular distributions of electrons ejected from these processes are measured systematically. Energy dependence of branching ratios and anisotropy parameters within the auto-ionization spectra are carefully analyzed, followed by a qualitative interpretation. (paper)

Branching structure and strain hardening of branched metallocene polyethylenes

International Nuclear Information System (INIS)

Torres, Enrique; Li, Si-Wan; Costeux, Stéphane; Dealy, John M.

2015-01-01

There have been a number of studies of a series of branched metallocene polyethylenes (BMPs) made in a solution, continuous stirred tank reactor (CSTR) polymerization. The materials studied vary in branching level in a systematic way, and the most highly branched members of the series exhibit mild strain hardening. An outstanding question is which types of branched molecules are responsible for strain hardening in extension. This question is explored here by use of polymerization and rheological models along with new data on the extensional flow behavior of the most highly branched members of the set. After reviewing all that is known about the effects of various branching structures in homogeneous polymers and comparing this with the structures predicted to be present in BMPs, it is concluded that in spite of their very low concentration, treelike molecules with branch-on-branch structure provide a large number of deeply buried inner segments that are essential for strain hardening in these polymers

Branching structure and strain hardening of branched metallocene polyethylenes

Energy Technology Data Exchange (ETDEWEB)

Torres, Enrique; Li, Si-Wan; Costeux, Stéphane; Dealy, John M., E-mail: john.dealy@mcgill.ca [Department of Chemical Engineering, McGill University, Montreal, Quebec H3A 0C4 (Canada)

2015-09-15

There have been a number of studies of a series of branched metallocene polyethylenes (BMPs) made in a solution, continuous stirred tank reactor (CSTR) polymerization. The materials studied vary in branching level in a systematic way, and the most highly branched members of the series exhibit mild strain hardening. An outstanding question is which types of branched molecules are responsible for strain hardening in extension. This question is explored here by use of polymerization and rheological models along with new data on the extensional flow behavior of the most highly branched members of the set. After reviewing all that is known about the effects of various branching structures in homogeneous polymers and comparing this with the structures predicted to be present in BMPs, it is concluded that in spite of their very low concentration, treelike molecules with branch-on-branch structure provide a large number of deeply buried inner segments that are essential for strain hardening in these polymers.

Parallel sorting algorithms

CERN Document Server

Akl, Selim G

1985-01-01

Parallel Sorting Algorithms explains how to use parallel algorithms to sort a sequence of items on a variety of parallel computers. The book reviews the sorting problem, the parallel models of computation, parallel algorithms, and the lower bounds on the parallel sorting problems. The text also presents twenty different algorithms, such as linear arrays, mesh-connected computers, cube-connected computers. Another example where algorithm can be applied is on the shared-memory SIMD (single instruction stream multiple data stream) computers in which the whole sequence to be sorted can fit in the

Pen Branch Delta and Savannah River Swamp Hydraulic Model

International Nuclear Information System (INIS)

Chen, K.F.

1999-01-01

The proposed Savannah River Site (SRS) Wetlands Restoration Project area is located in Barnwell County, South Carolina on the southwestern boundary of the SRS Reservation. The swamp covers about 40.5 km2 and is bounded to the west and south by the Savannah River and to the north and east by low bluffs at the edge of the Savannah River floodplain. Water levels within the swamp are determined by stage along the Savannah River, local drainage, groundwater seepage, and inflows from four tributaries, Beaver Dam Creek, Fourmile Branch, Pen Branch, and Steel Creek. Historic discharges of heated process water into these tributaries scoured the streambed, created deltas in the adjacent wetland, and killed native vegetation in the vicinity of the delta deposits. Future releases from these tributaries will be substantially smaller and closer to ambient temperatures. One component of the proposed restoration project will be to reestablish indigenous wetland vegetation on the Pen Branch delta that covers about 1.0 km2. Long-term predictions of water levels within the swamp are required to determine the characteristics of suitable plants. The objective of the study was to predict water levels at various locations within the proposed SRS Wetlands Restoration Project area for a range of Savannah River flows and regulated releases from Pen Branch. TABS-MD, a United States Army Corps of Engineer developed two-dimensional finite element open channel hydraulic computer code, was used to model the SRS swamp area for various flow conditions

Precise Propagation of Upper and Lower Probability Bounds in System P

OpenAIRE

Gilio, Angelo

2000-01-01

In this paper we consider the inference rules of System P in the framework of coherent imprecise probabilistic assessments. Exploiting our algorithms, we propagate the lower and upper probability bounds associated with the conditional assertions of a given knowledge base, automatically obtaining the precise probability bounds for the derived conclusions of the inference rules. This allows a more flexible and realistic use of System P in default reasoning and provides an exact illustration of ...

Bound constrained quadratic programming via piecewise

DEFF Research Database (Denmark)

Madsen, Kaj; Nielsen, Hans Bruun; Pinar, M. C.

1999-01-01

of a symmetric, positive definite matrix, and is solved by Newton iteration with line search. The paper describes the algorithm and its implementation including estimation of lambda/sub 1/ , how to get a good starting point for the iteration, and up- and downdating of Cholesky factorization. Results of extensive......We consider the strictly convex quadratic programming problem with bounded variables. A dual problem is derived using Lagrange duality. The dual problem is the minimization of an unconstrained, piecewise quadratic function. It involves a lower bound of lambda/sub 1/ , the smallest eigenvalue...

Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures

DEFF Research Database (Denmark)

Foshammer, Louise; Larsen, Kim Guldstrand; Mariegaard, Anders

2016-01-01

This paper concerns branching simulation for weighted Kripke structures with parametric weights. Concretely, we consider a weighted extension of branching simulation where a single transitions can be matched by a sequence of transitions while preserving the branching behavior. We relax this notion...... to allow for a small degree of deviation in the matching of weights, inducing a directed distance on states. The distance between two states can be used directly to relate properties of the states within a sub-fragment of weighted CTL. The problem of relating systems thus changes to minimizing the distance...... which, in the general parametric case, corresponds to finding suitable parameter valuations such that one system can approximately simulate another. Although the distance considers a potentially infinite set of transition sequences we demonstrate that there exists an upper bound on the length...

SkyAlign: a portable, work-efficient skyline algorithm for multicore and GPU architectures

DEFF Research Database (Denmark)

Bøgh, Kenneth Sejdenfaden; Chester, Sean; Assent, Ira

2016-01-01

The skyline operator determines points in a multidimensional dataset that offer some optimal trade-off. State-of-the-art CPU skyline algorithms exploit quad-tree partitioning with complex branching to minimise the number of point-to-point comparisons. Branch-phobic GPU skyline algorithms rely on ...... native multicore state of the art on challenging workloads by an increasing margin as more cores and sockets are utilised....

A Finite Continuation Algorithm for Bound Constrained Quadratic Programming

DEFF Research Database (Denmark)

Madsen, Kaj; Nielsen, Hans Bruun; Pinar, Mustafa C.

1999-01-01

The dual of the strictly convex quadratic programming problem with unit bounds is posed as a linear $\\ell_1$ minimization problem with quadratic terms. A smooth approximation to the linear $\\ell_1$ function is used to obtain a parametric family of piecewise-quadratic approximation problems...

Robust stability analysis of adaptation algorithms for single perceptron.

Science.gov (United States)

Hui, S; Zak, S H

1991-01-01

The problem of robust stability and convergence of learning parameters of adaptation algorithms in a noisy environment for the single preceptron is addressed. The case in which the same input pattern is presented in the adaptation cycle is analyzed. The algorithm proposed is of the Widrow-Hoff type. It is concluded that this algorithm is robust. However, the weight vectors do not necessarily converge in the presence of measurement noise. A modified version of this algorithm in which the reduction factors are allowed to vary with time is proposed, and it is shown that this algorithm is robust and that the weight vectors converge in the presence of bounded noise. Only deterministic-type arguments are used in the analysis. An ultimate bound on the error in terms of a convex combination of the initial error and the bound on the noise is obtained.

The K tree score: quantification of differences in the relative branch length and topology of phylogenetic trees.

Science.gov (United States)

Soria-Carrasco, Víctor; Talavera, Gerard; Igea, Javier; Castresana, Jose

2007-11-01

We introduce a new phylogenetic comparison method that measures overall differences in the relative branch length and topology of two phylogenetic trees. To do this, the algorithm first scales one of the trees to have a global divergence as similar as possible to the other tree. Then, the branch length distance, which takes differences in topology and branch lengths into account, is applied to the two trees. We thus obtain the minimum branch length distance or K tree score. Two trees with very different relative branch lengths get a high K score whereas two trees that follow a similar among-lineage rate variation get a low score, regardless of the overall rates in both trees. There are several applications of the K tree score, two of which are explained here in more detail. First, this score allows the evaluation of the performance of phylogenetic algorithms, not only with respect to their topological accuracy, but also with respect to the reproduction of a given branch length variation. In a second example, we show how the K score allows the selection of orthologous genes by choosing those that better follow the overall shape of a given reference tree. http://molevol.ibmb.csic.es/Ktreedist.html

Quantum lower bound for sorting

OpenAIRE

Shi, Yaoyun

2000-01-01

We prove that \\Omega(n log(n)) comparisons are necessary for any quantum algorithm that sorts n numbers with high success probability and uses only comparisons. If no error is allowed, at least 0.110nlog_2(n) - 0.067n + O(1) comparisons must be made. The previous known lower bound is \\Omega(n).

Marginal Consistency: Upper-Bounding Partition Functions over Commutative Semirings.

Science.gov (United States)

Werner, Tomás

2015-07-01

Many inference tasks in pattern recognition and artificial intelligence lead to partition functions in which addition and multiplication are abstract binary operations forming a commutative semiring. By generalizing max-sum diffusion (one of convergent message passing algorithms for approximate MAP inference in graphical models), we propose an iterative algorithm to upper bound such partition functions over commutative semirings. The iteration of the algorithm is remarkably simple: change any two factors of the partition function such that their product remains the same and their overlapping marginals become equal. In many commutative semirings, repeating this iteration for different pairs of factors converges to a fixed point when the overlapping marginals of every pair of factors coincide. We call this state marginal consistency. During that, an upper bound on the partition function monotonically decreases. This abstract algorithm unifies several existing algorithms, including max-sum diffusion and basic constraint propagation (or local consistency) algorithms in constraint programming. We further construct a hierarchy of marginal consistencies of increasingly higher levels and show than any such level can be enforced by adding identity factors of higher arity (order). Finally, we discuss instances of the framework for several semirings, including the distributive lattice and the max-sum and sum-product semirings.

The bounded model property via step algebras and step frames

NARCIS (Netherlands)

Bezhanishvili, N.; Ghilardi, S.

2014-01-01

The paper introduces semantic and algorithmic methods for establishing a variant of the analytic subformula property (called ‘the bounded proof property’, bpp) for modal propositional logics. The bpp is much weaker property than full cut-elimination, but it is nevertheless sufficient for

Effective calculation algorithm for nuclear chains of arbitrary length and branching

International Nuclear Information System (INIS)

Chirkov, V.A.; Mishanin, B.V.

1994-01-01

An effective algorithm for calculation of the isotope concentration in the spent nuclear fuel when it is kept in storage, is presented. Using the superposition principle and representing the transfer function in a rather compact form it becomes possible achieve high calculation speed and a moderate computer code size. The algorithm is applied for the calculation of activity, energy release and toxicity of heavy nuclides and products of their decay when the fuel is kept in storage. (authors). 1 ref., 4 tabs

Properties of Confined Star-Branched and Linear Chains. A Monte Carlo Simulation Study

International Nuclear Information System (INIS)

Romiszowski, P.; Sikorski, A.

2004-01-01

A model of linear and star-branched polymer chains confined between two parallel and impenetrable surfaces was built. The polymer chains were restricted to a simple cubic lattice. Two macromolecular architectures of the chain: linear and star branched (consisted of f = 3 branches of equal length) were studied. The excluded volume was the only potential introduced into the model (the athermal system). Monte Carlo simulations were carried out using a sampling algorithm based on chain's local changes of conformation. The simulations were carried out at different confinement conditions: from light to high chain's compression. The scaling of chain's size with the chain length was studied and discussed. The influence of the confinement and the macromolecular architecture on the shape of a chain was studied. The differences in the shape of linear and star-branched chains were pointed out. (author)

Bound Alternative Direction Optimization for Image Deblurring

Directory of Open Access Journals (Sweden)

Xiangrong Zeng

2014-01-01

the ℓp regularizer by a novel majorizer and then, based on a variable splitting, to reformulate the bound unconstrained problem into a constrained one, which is then addressed via an augmented Lagrangian method. The proposed algorithm actually combines the reweighted ℓ1 minimization method and the alternating direction method of multiples (ADMM such that it succeeds in extending the application of ADMM to ℓp minimization problems. The conducted experimental studies demonstrate the superiority of the proposed algorithm for the synthesis ℓp minimization over the state-of-the-art algorithms for the synthesis ℓ1 minimization on image deblurring.

A Branch-and-Price algorithm for railway rolling stock rescheduling

DEFF Research Database (Denmark)

Lusby, Richard Martin; Haahr, Jørgen Thorlund; Larsen, Jesper

2017-01-01

How to best reschedule their fleet of rolling stock units during a disruption is an optimization problem regularly faced by railway operators. Despite the problem’s high complexity, it is still usually solved manually. In this paper we propose a path based mathematical formulation and solve...... by the suburban railway operator in Copenhagen, DSB S-tog. When used in combination with a lower bound method taken from the literature we show that near-optimal solutions to this rescheduling problem can be found within a few seconds. Furthermore, we show that the proposed methodology can be used, with minor...

On utilization bounds for a periodic resource under rate monotonic scheduling

NARCIS (Netherlands)

Renssen, van A.M.; Geuns, S.J.; Hausmans, J.P.H.M.; Poncin, W.; Bril, R.J.

2009-01-01

This paper revisits utilization bounds for a periodic resource under the rate monotonic (RM) scheduling algorithm. We show that the existing utilization bound, as presented in [8, 9], is optimistic. We subsequently show that by viewing the unavailability of the periodic resource as a deferrable

Forecasting with Universal Approximators and a Learning Algorithm

DEFF Research Database (Denmark)

Kock, Anders Bredahl

bounds for the combination rules applied. We apply the Weighted Average Algorithm (WAA) of Kivinen and Warmuth (1999) for which such loss bounds exist. Specifically, one can bound the worst case performance of the WAA compared to the performance of the best single model in the set of models combined from....... The use of universal approximators along with a combination scheme for which explicit loss bounds exist should give a solid theoretical foundation to the way the forecasts are performed. The practical performance will be investigated by considering various monthly postwar macroeconomic data sets for the G...

A simple algorithm for computing the smallest enclosing circle

DEFF Research Database (Denmark)

Skyum, Sven

1991-01-01

Presented is a simple O(n log n) algorithm for computing the smallest enclosing circle of a convex polygon. It can be easily extended to algorithms that compute the farthest-and the closest-point Voronoi diagram of a convex polygon within the same time bound.......Presented is a simple O(n log n) algorithm for computing the smallest enclosing circle of a convex polygon. It can be easily extended to algorithms that compute the farthest-and the closest-point Voronoi diagram of a convex polygon within the same time bound....

Model-Independent Lower Bounds for $b \\to d$ Penguin Processes

CERN Document Server

Fleischer, Robert; Fleischer, Robert; Recksiegel, Stefan

2005-01-01

For the exploration of flavour physics, b -> d penguin processes are an important aspect, with the prominent example of \\bar B^0_d -> K^0 \\bar K^0. We recently derived lower bounds for the CP-averaged branching ratio of this channel in the Standard Model; they were found to be very close to the corresponding experimental upper limits, thereby suggesting that \\bar B^0_d -> K^0 \\bar K^0 should soon be observed. In fact, the BaBar collaboration subsequently announced the first signals of this transition. Here we point out that it is also possible to derive lower bounds for \\bar B -> \\rho \\gamma decays, which are again surprisingly close to the current experimental upper limits. We show that these bounds are realizations of a general bound that holds within the Standard Model for b -> d penguin processes, allowing further applications to decays of the kind B^\\pm -> K^{(\\ast)\\pm} K^{(\\ast)} and B^\\pm -> \\pi^\\pm \\ell^+ \\ell^-, \\rho^\\pm \\ell^+ \\ell^-.

Total-variation regularization with bound constraints

International Nuclear Information System (INIS)

Chartrand, Rick; Wohlberg, Brendt

2009-01-01

We present a new algorithm for bound-constrained total-variation (TV) regularization that in comparison with its predecessors is simple, fast, and flexible. We use a splitting approach to decouple TV minimization from enforcing the constraints. Consequently, existing TV solvers can be employed with minimal alteration. This also makes the approach straightforward to generalize to any situation where TV can be applied. We consider deblurring of images with Gaussian or salt-and-pepper noise, as well as Abel inversion of radiographs with Poisson noise. We incorporate previous iterative reweighting algorithms to solve the TV portion.

ANALYSIS AND PERFORMANCE MEASUREMENT OF EXISTING SOLUTION METHODS OF QUADRATIC ASSIGNMENT PROBLEM

Directory of Open Access Journals (Sweden)

Morteza KARAMI

2014-01-01

Full Text Available Quadratic Assignment Problem (QAP is known as one of the most difficult combinatorial optimization problems that is classified in the category of NP-hard problems. Quadratic Assignment Problem Library (QAPLIB is a full database of QAPs which contains several problems from different authors and different sizes. Many exact and meta-heuristic solution methods have been introduced to solve QAP. In this study we focus on previously introduced solution methods of QAP e.g. Branch and Bound (B&B, Simulated Annealing (SA Algorithm, Greedy Randomized Adaptive Search Procedure (GRASP for dense and sparse QAPs. The codes of FORTRAN for these methods were downloaded from QAPLIB. All problems of QAPLIB were solved by the abovementioned methods. Several results were obtained from the computational experiments part. The Results show that the Branch and Bound method is able to introduce a feasible solution for all problems while Simulated Annealing Algorithm and GRASP methods are not able to find any solution for some problems. On the other hand, Simulated Annealing and GRASP methods have shorter run time comparing to the Branch and Bound method. In addition, the performance of the methods on the objective function value is discussed.

A Note on Lower Bounds for Colourful Simplicial Depth

Directory of Open Access Journals (Sweden)

Antoine Deza

2013-01-01

Full Text Available The colourful simplicial depth problem in dimension d is to find a configuration of (d+1 sets of (d+1 points such that the origin is contained in the convex hull of each set, or colour, but contained in a minimal number of colourful simplices generated by taking one point from each set. A construction attaining d2 + 1 simplices is known, and is conjectured to be minimal. This has been confirmed up to d = 3, however the best known lower bound for d ≥ 4 is ⌈(d+12 /2 ⌉. In this note, we use a branching strategy to improve the lower bound in dimension 4 from 13 to 14.

A duality approach for solving bounded linear programming problems with fuzzy variables based on ranking functions and its application in bounded transportation problems

Science.gov (United States)

Ebrahimnejad, Ali

2015-08-01

There are several methods, in the literature, for solving fuzzy variable linear programming problems (fuzzy linear programming in which the right-hand-side vectors and decision variables are represented by trapezoidal fuzzy numbers). In this paper, the shortcomings of some existing methods are pointed out and to overcome these shortcomings a new method based on the bounded dual simplex method is proposed to determine the fuzzy optimal solution of that kind of fuzzy variable linear programming problems in which some or all variables are restricted to lie within lower and upper bounds. To illustrate the proposed method, an application example is solved and the obtained results are given. The advantages of the proposed method over existing methods are discussed. Also, one application of this algorithm in solving bounded transportation problems with fuzzy supplies and demands is dealt with. The proposed method is easy to understand and to apply for determining the fuzzy optimal solution of bounded fuzzy variable linear programming problems occurring in real-life situations.

Forecasting with Universal Approximators and a Learning Algorithm

DEFF Research Database (Denmark)

Kock, Anders Bredahl

2011-01-01

to the performance of the best single model in the set of models combined from. The use of universal approximators along with a combination scheme for which explicit loss bounds exist should give a solid theoretical foundation to the way the forecasts are performed. The practical performance will be investigated...... combination has a long history in econometrics focus has not been on proving loss bounds for the combination rules applied. We apply the Weighted Average Algorithm (WAA) of Kivinen & Warmuth (1999) for which such loss bounds exist. Specifically, one can bound the worst case performance of the WAA compared...

A comparative study of fingerprint thinning algorithms

CSIR Research Space (South Africa)

Khanyile, NP

2011-08-01

Full Text Available are compared in terms of the quality of the skeletons they produce (i.e. connectivity and spurious branches) as well as the time complexity associated with each algorithm. Results show that faster algorithms have difficulty preserving connectivity. Zhang...

Rate Reduction for State-labelled Markov Chains with Upper Time-bounded CSL Requirements

Directory of Open Access Journals (Sweden)

Bharath Siva Kumar Tati

2016-07-01

Full Text Available This paper presents algorithms for identifying and reducing a dedicated set of controllable transition rates of a state-labelled continuous-time Markov chain model. The purpose of the reduction is to make states to satisfy a given requirement, specified as a CSL upper time-bounded Until formula. We distinguish two different cases, depending on the type of probability bound. A natural partitioning of the state space allows us to develop possible solutions, leading to simple algorithms for both cases.

A Forward Reachability Algorithm for Bounded Timed-Arc Petri Nets

DEFF Research Database (Denmark)

David, Alexandre; Jacobsen, Lasse; Jacobsen, Morten

2012-01-01

Timed-arc Petri nets (TAPN) are a well-known time extension of thePetri net model and several translations to networks of timedautomata have been proposed for this model.We present a direct, DBM-basedalgorithm for forward reachability analysis of bounded TAPNs extended with transport arcs...

Cryptographic protocol security analysis based on bounded constructing algorithm

Institute of Scientific and Technical Information of China (English)

无

2006-01-01

An efficient approach to analyzing cryptographic protocols is to develop automatic analysis tools based on formal methods. However, the approach has encountered the high computational complexity problem due to reasons that participants of protocols are arbitrary, their message structures are complex and their executions are concurrent. We propose an efficient automatic verifying algorithm for analyzing cryptographic protocols based on the Cryptographic Protocol Algebra (CPA) model proposed recently, in which algebraic techniques are used to simplify the description of cryptographic protocols and their executions. Redundant states generated in the analysis processes are much reduced by introducing a new algebraic technique called Universal Polynomial Equation and the algorithm can be used to verify the correctness of protocols in the infinite states space. We have implemented an efficient automatic analysis tool for cryptographic protocols, called ACT-SPA, based on this algorithm, and used the tool to check more than 20 cryptographic protocols. The analysis results show that this tool is more efficient, and an attack instance not offered previously is checked by using this tool.

Scaling Limits and Generic Bounds for Exploration Processes

Science.gov (United States)

Bermolen, Paola; Jonckheere, Matthieu; Sanders, Jaron

2017-12-01

We consider exploration algorithms of the random sequential adsorption type both for homogeneous random graphs and random geometric graphs based on spatial Poisson processes. At each step, a vertex of the graph becomes active and its neighboring nodes become blocked. Given an initial number of vertices N growing to infinity, we study statistical properties of the proportion of explored (active or blocked) nodes in time using scaling limits. We obtain exact limits for homogeneous graphs and prove an explicit central limit theorem for the final proportion of active nodes, known as the jamming constant, through a diffusion approximation for the exploration process which can be described as a unidimensional process. We then focus on bounding the trajectories of such exploration processes on random geometric graphs, i.e., random sequential adsorption. As opposed to exploration processes on homogeneous random graphs, these do not allow for such a dimensional reduction. Instead we derive a fundamental relationship between the number of explored nodes and the discovered volume in the spatial process, and we obtain generic bounds for the fluid limit and jamming constant: bounds that are independent of the dimension of space and the detailed shape of the volume associated to the discovered node. Lastly, using coupling techinques, we give trajectorial interpretations of the generic bounds.

Asymptotically anti-de Sitter spacetimes and scalar fields with a logarithmic branch

International Nuclear Information System (INIS)

Henneaux, Marc; Martinez, Cristian; Troncoso, Ricardo; Zanelli, Jorge

2004-01-01

We consider a self-interacting scalar field whose mass saturates the Breitenlohner-Freedman bound, minimally coupled to Einstein gravity with a negative cosmological constant in D≥3 dimensions. It is shown that the asymptotic behavior of the metric has a slower fall-off than that of pure gravity with a localized distribution of matter, due to the back-reaction of the scalar field, which has a logarithmic branch decreasing as r -(D-1)/2 ln r for large radius r. We find the asymptotic conditions on the fields which are invariant under the same symmetry group as pure gravity with negative cosmological constant (conformal group in D-1 dimensions). The generators of the asymptotic symmetries are finite even when the logarithmic branch is considered but acquire, however, a contribution from the scalar field

Bounds on Average Time Complexity of Decision Trees

KAUST Repository

Chikalov, Igor

2011-01-01

In this chapter, bounds on the average depth and the average weighted depth of decision trees are considered. Similar problems are studied in search theory [1], coding theory [77], design and analysis of algorithms (e.g., sorting) [38]. For any

Distortion-Rate Bounds for Distributed Estimation Using Wireless Sensor Networks

Directory of Open Access Journals (Sweden)

Nihar Jindal

2008-03-01

Full Text Available We deal with centralized and distributed rate-constrained estimation of random signal vectors performed using a network of wireless sensors (encoders communicating with a fusion center (decoder. For this context, we determine lower and upper bounds on the corresponding distortion-rate (D-R function. The nonachievable lower bound is obtained by considering centralized estimation with a single-sensor which has all observation data available, and by determining the associated D-R function in closed-form. Interestingly, this D-R function can be achieved using an estimate first compress afterwards (EC approach, where the sensor (i forms the minimum mean-square error (MMSE estimate for the signal of interest; and (ii optimally (in the MSE sense compresses and transmits it to the FC that reconstructs it. We further derive a novel alternating scheme to numerically determine an achievable upper bound of the D-R function for general distributed estimation using multiple sensors. The proposed algorithm tackles an analytically intractable minimization problem, while it accounts for sensor data correlations. The obtained upper bound is tighter than the one determined by having each sensor performing MSE optimal encoding independently of the others. Numerical examples indicate that the algorithm performs well and yields D-R upper bounds which are relatively tight with respect to analytical alternatives obtained without taking into account the cross-correlations among sensor data.

JPLEX: Java Simplex Implementation with Branch-and-Bound Search for Automated Test Assembly

Science.gov (United States)

Park, Ryoungsun; Kim, Jiseon; Dodd, Barbara G.; Chung, Hyewon

2011-01-01

JPLEX, short for Java simPLEX, is an automated test assembly (ATA) program. It is a mixed integer linear programming (MILP) solver written in Java. It reads in a configuration file, solves the minimization problem, and produces an output file for postprocessing. It implements the simplex algorithm to create a fully relaxed solution and…

HiggsBounds 2.0.0. Confronting neutral and charged Higgs sector predictions with exclusion bounds from LEP and the Tevatron

Energy Technology Data Exchange (ETDEWEB)

Bechtle, P.; Weiglein, G. [Deutsches Elektronen-Synchrotron (DESY), Hamburg (Germany); Brein, O. [Freiburg Univ. (Germany). Physikalisches Inst.; Heinemeyer, S. [Instituto de Fisica de Cantabria (CSIC-UC), Santander (Spain); Williams, K.E. [Bonn Univ. (Germany). Bethe Center for Theoretical Physics

2011-03-15

HiggsBounds 2.0.0 is a computer code which tests both neutral and charged Higgs sectors of arbitrary models against the current exclusion bounds from the Higgs searches at LEP and the Tevatron. As input, it requires a selection of model predictions, such as Higgs masses, branching ratios, effective couplings and total decay widths. HiggsBounds 2.0.0 then uses the expected and observed topological cross section limits from the Higgs searches to determine whether a given parameter scenario of a model is excluded at the 95% C.L. by those searches. Version 2.0.0 represents a significant extension of the code since its first release (1.0.0). It includes now 28/53 LEP/Tevatron Higgs search analyses, compared to the 11/22 in the first release, of which many of the ones from the Tevatron are replaced by updates. As a major extension, the code allows now the predictions for (singly) charged Higgs bosons to be confronted with LEP and Tevatron searches. Furthermore, the newly included analyses contain LEP searches for neutral Higgs bosons (H) decaying invisibly or into (non flavour tagged) hadrons as well as decay-mode independent searches for neutral Higgs bosons, LEP searches via the production modes {tau}{sup +}{tau}{sup -}H and b anti bH, and Tevatron searches via t anti tH. Also, all Tevatron results presented at the ICHEP'10 are included in version 2.0.0. As physics applications of HiggsBounds 2.0.0 we study the allowed Higgs mass range for model scenarios with invisible Higgs decays and we obtain exclusion results for the scalar sector of the Randall-Sundrum model using up-to-date LEP and Tevatron direct search results. (orig.)

Non-convex multi-objective optimization

CERN Document Server

Pardalos, Panos M; Žilinskas, Julius

2017-01-01

Recent results on non-convex multi-objective optimization problems and methods are presented in this book, with particular attention to expensive black-box objective functions. Multi-objective optimization methods facilitate designers, engineers, and researchers to make decisions on appropriate trade-offs between various conflicting goals. A variety of deterministic and stochastic multi-objective optimization methods are developed in this book. Beginning with basic concepts and a review of non-convex single-objective optimization problems; this book moves on to cover multi-objective branch and bound algorithms, worst-case optimal algorithms (for Lipschitz functions and bi-objective problems), statistical models based algorithms, and probabilistic branch and bound approach. Detailed descriptions of new algorithms for non-convex multi-objective optimization, their theoretical substantiation, and examples for practical applications to the cell formation problem in manufacturing engineering, the process design in...

An corrigendum on the paper : Solving the job-shop scheduling problem optimally by dynamic programming (Computers and Operations Research 39(12) (2968–2977) (S0305054812000500) (10.1016/j.cor.2012.02.024))

NARCIS (Netherlands)

van Hoorn, Jelke J.; Nogueira, Agustín; Ojea, Ignacio; Gromicho Dos Santos, Joaquim Antonio

2017-01-01

In [1] an algorithm is proposed for solving the job-shop scheduling problem optimally using a dynamic programming strategy. This is, according to our knowledge, the first exact algorithm for the Job Shop problem which is not based on integer linear programming and branch and bound. Despite the

Improved QRD-M Detection Algorithm for Generalized Spatial Modulation Scheme

Directory of Open Access Journals (Sweden)

Xiaorong Jing

2017-01-01

Full Text Available Generalized spatial modulation (GSM is a spectral and energy efficient multiple-input multiple-output (MIMO transmission scheme. It will lead to imperfect detection performance with relatively high computational complexity by directly applying the original QR-decomposition with M algorithm (QRD-M to the GSM scheme. In this paper an improved QRD-M algorithm is proposed for GSM signal detection, which achieves near-optimal performance but with relatively low complexity. Based on the QRD, the improved algorithm firstly transforms the maximum likelihood (ML detection of the GSM signals into searching an inverted tree structure. Then, in the searching process of the M branches, the branches corresponding to the illegitimate transmit antenna combinations (TACs and related to invalid number of active antennas are cut in order to improve the validity of the resultant branches at each level by taking advantage of characteristics of GSM signals. Simulation results show that the improved QRD-M detection algorithm provides similar performance to maximum likelihood (ML with the reduced computational complexity compared to the original QRD-M algorithm, and the optimal value of parameter M of the improved QRD-M algorithm for detection of the GSM scheme is equal to modulation order plus one.

A general algorithm for radioactive decay with branching and loss from a medium

International Nuclear Information System (INIS)

Strenge, D.L.

1995-07-01

Many areas in the field of health physics require evaluation of the change of radionuclide quantity in a medium with time. A general solution to first-order compartmental models is presented in this paper for application to systems consisting of one physical medium that contains any number of radionuclide decay chain members. The general analytical solution to the problem is first described mathematically, and then extended to four applications: (1) evaluation of the quantity of radionuclides as a function of time, (2) evaluation of the time integral of the quantity during a time period, (3) evaluation of the amount in a medium as a function of time following deposition at a constant rate, and (4) evaluation of the time integral of the amount in a medium after deposition at a constant rate for a time. The solution can be applied to any system involving physical transfers from the medium and radioactive chain decay with branching in the medium. The general solution is presented for quantities expressed in units of atoms and activity. Unlike many earlier mathematical solutions, this solution includes chain decay with branching explicitly in the equations

Development of a Grapevine Pruning Algorithm for Using in Pruning

Directory of Open Access Journals (Sweden)

S. M Hosseini

2017-10-01

Full Text Available Introduction Great areas of the orchards in the world are dedicated to cultivation of the grapevine. Normally grape vineyards are pruned twice a year. Among the operations of grape production, winter pruning of the bushes is the only operation that still has not been fully mechanized while it is known as the most laborious jobs in the farm. Some of the grape producing countries use various mechanical machines to prune the grapevines, but in most cases, these machines do not have a good performance. Therefore intelligent pruning machine seems to be necessary in this regard and this intelligent pruning machines can reduce the labor required to prune the vineyards. It this study in was attempted to develop an algorithm that uses image processing techniques to identify which parts of the grapevine should be cut. Stereo vision technique was used to obtain three dimensional images from the bare bushes whose leaves were fallen in autumn. Stereo vision systems are used to determine the depth from two images taken at the same time but from slightly different viewpoints using two cameras. Each pair of images of a common scene is related by a popular geometry, and corresponding points in the images pairs are constrained to lie on pairs of conjugate popular lines. Materials and Methods Photos were taken from gardens of the Research Center for Agriculture and Natural Resources of Fars province, Iran. At first, the distance between the plants and the cameras should be determined. The distance between the plants and cameras can be obtained by using the stereo vision techniques. Therefore, this method was used in this paper by two pictures taken from each plant with the left and right cameras. The algorithm was written in MATLAB. To facilitate the segmentation of the branches from the rows at the back, a blue plate with dimensions of 2×2 m2 were used at the background. After invoking the images, branches were segmented from the background to produce the binary

Autonomous Positioning Techniques Based on Cramér-Rao Lower Bound Analysis

Directory of Open Access Journals (Sweden)

Urruela Andreu

2006-01-01

Full Text Available We consider the problem of autonomously locating a number of asynchronous sensor nodes in a wireless network. A strong focus lies on reducing the processing resources needed to solve the relative positioning problem, an issue of great interest in resource-constrained wireless sensor networks. In the first part of the paper, based on a well-known derivation of the Cramér-Rao lower bound for the asynchronous sensor positioning problem, we are able to construct optimal preprocessing methods for sensor clock-offset cancellation. A cancellation of unknown clock-offsets from the asynchronous positioning problem reduces processing requirements, and, under certain reasonable assumptions, allows for statistically efficient distributed positioning algorithms. Cramér-Rao lower bound theory may also be used for estimating the performance of a positioning algorithm. In the second part of this paper, we exploit this property in developing a distributed algorithm, where the global positioning problem is solved suboptimally, using a divide-and-conquer approach of low complexity. The performance of this suboptimal algorithm is evaluated through computer simulation, and compared to previously published algorithms.

On the Coulomb and Higgs branch formulae for multi-centered black holes and quiver invariants

CERN Document Server

Manschot, Jan; Sen, Ashoke

2013-01-01

In previous work we have shown that the equivariant index of multi-centered N=2 black holes localizes on collinear configurations along a fixed axis. Here we provide a general algorithm for enumerating such collinear configurations and computing their contribution to the index. We apply this machinery to the case of black holes described by quiver quantum mechanics, and give a systematic prescription -- the Coulomb branch formula -- for computing the cohomology of the moduli space of quiver representations. For quivers without oriented loops, the Coulomb branch formula is shown to agree with the Higgs branch formula based on Reineke's result for stack invariants, even when the dimension vector is not primitive. For quivers with oriented loops, the Coulomb branch formula parametrizes the Poincar\\'e polynomial of the quiver moduli space in terms of single-centered (or pure-Higgs) BPS invariants, which are conjecturally independent of the stability condition (i.e. the choice of Fayet-Iliopoulos parameters) and a...

Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

DEFF Research Database (Denmark)

Oliveto, Pietro S.; Witt, Carsten

2011-01-01

Drift analysis is a powerful tool used to bound the optimization time of evolutionary algorithms (EAs). Various previous works apply a drift theorem going back to Hajek in order to show exponential lower bounds on the optimization time of EAs. However, this drift theorem is tedious to read...... and to apply since it requires two bounds on the moment-generating (exponential) function of the drift. A recent work identifies a specialization of this drift theorem that is much easier to apply. Nevertheless, it is not as simple and not as general as possible. The present paper picks up Hajek’s line...

Achieving Agreement in Three Rounds with Bounded-Byzantine Faults

Science.gov (United States)

Malekpour, Mahyar, R.

2017-01-01

A three-round algorithm is presented that guarantees agreement in a system of K greater than or equal to 3F+1 nodes provided each faulty node induces no more than F faults and each good node experiences no more than F faults, where, F is the maximum number of simultaneous faults in the network. The algorithm is based on the Oral Message algorithm of Lamport, Shostak, and Pease and is scalable with respect to the number of nodes in the system and applies equally to traditional node-fault model as well as the link-fault model. We also present a mechanical verification of the algorithm focusing on verifying the correctness of a bounded model of the algorithm as well as confirming claims of determinism.

BCDP: Budget Constrained and Delay-Bounded Placement for Hybrid Roadside Units in Vehicular Ad Hoc Networks

Directory of Open Access Journals (Sweden)

Peng Li

2014-11-01

Full Text Available In vehicular ad hoc networks, roadside units (RSUs placement has been proposed to improve the the overall network performance in many ITS applications. This paper addresses the budget constrained and delay-bounded placement problem (BCDP for roadside units in vehicular ad hoc networks. There are two types of RSUs: cable connected RSU (c-RSU and wireless RSU (w-RSU. c-RSUs are interconnected through wired lines, and they form the backbone of VANETs, while w-RSUs connect to other RSUs through wireless communication and serve as an economical extension of the coverage of c-RSUs. The delay-bounded coverage range and deployment cost of these two cases are totally different. We are given a budget constraint and a delay bound, the problem is how to find the optimal candidate sites with the maximal delay-bounded coverage to place RSUs such that a message from any c-RSU in the region can be disseminated to the more vehicles within the given budget constraint and delay bound. We first prove that the BCDP problem is NP-hard. Then we propose several algorithms to solve the BCDP problem. Simulation results show the heuristic algorithms can significantly improve the coverage range and reduce the total deployment cost, compared with other heuristic methods.

The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach

DEFF Research Database (Denmark)

Hansen, Anders Dohn; Kolind, Esben; Clausen, Jens

2009-01-01

In this paper, we consider the Manpower Allocation Problem with Time Windows, Job-Teaming Constraints and a limited number of teams (m-MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks....... Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must initiate execution simultaneously. We present an IP-model for the problem, which is decomposed using Dantzig-Wolfe decomposition....... The problem is solved by column generation in a Branch-and-Price framework. Simultaneous execution of tasks is enforced by the branching scheme. To test the efficiency of the proposed algorithm, 12 realistic test instances are introduced. The algorithm is able to find the optimal solution in 11 of the test...

Generalized bounds for convex multistage stochastic programs

CERN Document Server

Künzi, H; Fandel, G; Trockel, W; Basile, A; Drexl, A; Dawid, H; Inderfurth, K; Kürsten, W; Schittko, U

2005-01-01

This work was completed during my tenure as a scientific assistant and d- toral student at the Institute for Operations Research at the University of St. Gallen. During that time, I was involved in several industry projects in the field of power management, on the occasion of which I was repeatedly c- fronted with complex decision problems under uncertainty. Although usually hard to solve, I quickly learned to appreciate the benefit of stochastic progr- ming models and developed a strong interest in their theoretical properties. Motivated both by practical questions and theoretical concerns, I became p- ticularly interested in the art of finding tight bounds on the optimal value of a given model. The present work attempts to make a contribution to this important branch of stochastic optimization theory. In particular, it aims at extending some classical bounding methods to broader problem classes of practical relevance. This book was accepted as a doctoral thesis by the University of St. Gallen in June 2004.1...

Branching microtubule nucleation in Xenopus egg extracts mediated by augmin and TPX2

Science.gov (United States)

Petry, Sabine; Groen, Aaron C.; Ishihara, Keisuke; Mitchison, Timothy J.; Vale, Ronald D.

2013-01-01

Summary The microtubules that comprise mitotic spindles in animal cells are nucleated at centrosomes and by spindle assembly factors that are activated in the vicinity of chromatin. Indirect evidence also has suggested that microtubules might be nucleated from pre-existing microtubules throughout the spindle, but this process has not been observed directly. Here, we demonstrate microtubule nucleation from the sides of existing microtubules in meiotic Xenopus egg extracts. Daughter microtubules grow at a low branch angle and with the same polarity as mother filaments. Branching microtubule nucleation requires gamma-tubulin and augmin and is stimulated by GTP-bound Ran and its effector TPX2, factors previously implicated in chromatin-stimulated nucleation. Because of the rapid amplification of microtubule numbers and the preservation of microtubule polarity, microtubule-dependent microtubule nucleation is well suited for spindle assembly and maintenance. PMID:23415226

Dynamic Properties of Star-Branched Polymer Brushes

International Nuclear Information System (INIS)

Sikorski, A.; Romiszowski, P.

2004-01-01

We studied a simplified model of a polymer brush. It consisted of star-branched chains, which were restricted to a simple cubic lattice. Each star-branched macromolecule consisted of three linear arms of equal length emanating from a common origin (the branching point). The chains were grafted to an impenetrable surface, i.e. they were terminally attached to the surface with one arm. The number of chains was varied from low to high grafting density. The model system was studied at good solvent conditions because the excluded volume effect was the only potential of interaction included in the model. The properties of this model system were studied by means of Monte Carlo simulation. The sampling algorithm was based on local changes of chain conformations. The dynamic properties of the polymer brush were studied and correlated with its structure. The differences in relaxation times of particular star arms were shown. The short-time mobility of polymer layers was analyzed. The lateral self-diffusion of chains was also studied and discussed. (author)

Occurrence and distribution of GDGTs in the free and bound lipid fractions from podzols: implications for the reconstruction of mean air temperature

Science.gov (United States)

Huguet, A.; Fosse, C.; Metzger, P.; Derenne, S.

2009-12-01

Glycerol dialkyl glycerol tetraethers (GDGTs) are complex lipids of high molecular weight, present in cell membranes of archaea and some bacteria. Archaeal membranes are formed predominantly by isoprenoid GDGTs with acyclic or ring-containing biphytanyl chains. Another type of GDGTs with branched instead of isoprenoid alkyl chains was recently discovered in soils. Branched tetraethers were suggested to be produced by anaerobic bacteria and can be used to reconstruct past air temperature and soil pH. Lipids preserved in soils can take two broad chemical forms: "free" lipids, recoverable after solvent extraction, and "bound" lipids, linked to the organic or mineral matrix of soils. The "free" and "bound" lipid fractions may respond to environmental changes in different ways and the information derived from these two pools may differ. The aim of the present work was therefore to compare the abundance and distribution of "free" and "bound" GDGTs in two contrasted podzols: a temperate podzol located 40 km north of Paris and a tropical podzol from the upper Amazon Basin. Five samples were collected from the whole profile of the temperate podzol including the litter layer. Five additional samples were obtained from three profiles of the tropical soil sequence, representative of the transition between a latosol and a well-developed podzol. Vertical and/or lateral variations in GDGT content and composition were highlighted. In particular, in the tropical sequence, GDGTs were present at relatively low concentrations in the early stages of podzolisation and were more abundant in the well-developed podzolic horizons, where higher acidity and increased bacterial activity may favour their stabilization. Concerning the temperate podzol, GDGT distribution was shown to vary greatly with depth in the soil profile, the methylation degree of bacterial GDGTs being notably higher in the surficial than in the deep soil horizons. Bacterial GDGTs were also detected in the litter layer of

Graphs and matroids weighted in a bounded incline algebra.

Science.gov (United States)

Lu, Ling-Xia; Zhang, Bei

2014-01-01

Firstly, for a graph weighted in a bounded incline algebra (or called a dioid), a longest path problem (LPP, for short) is presented, which can be considered the uniform approach to the famous shortest path problem, the widest path problem, and the most reliable path problem. The solutions for LPP and related algorithms are given. Secondly, for a matroid weighted in a linear matroid, the maximum independent set problem is studied.

The influence of flexible branches in flexible polymers

International Nuclear Information System (INIS)

Wescott, J.T.

1998-06-01

In this work the influence of branches in flexible polymer systems has been investigated by consideration of (1) the behaviour of isolated poly-α-olefin chains and (2) the p -T phase behaviour of poly(4-methylpentene-1)(P4MP1). Molecular dynamics simulations of isolated poly-α-olefins were performed in order to gauge directly the effect of molecular structure on chain dimensions, flexibility (via the persistence length) and shape. Under Θ-conditions the addition of short linear branches was shown to increase the flexibility of the backbone. In conditions of good solvent, however, the effect of longer and bulkier branches was to increase the persistence length and average size of the coil with the arrangement of side chain atoms making a small difference. The side branches themselves also affected the solvent conditions experienced by the backbone, behaving much like bound solvent. Consideration of ethylene-α-olefin copolymers, where the branch content was varied from 0-50%, showed that under good solvent conditions the branches increased the chain stiffness only when the gap between side branches was less than five backbone carbon atoms. The backbone torsions were also shown to play an important role in determining these trends. For comparison with the above simulations, persistence length values for polyethylene (= 7.3±0.2A) and P4MP1 (=7.6±0.3A) were measured experimentally by neutron scattering in dilute solution. A value of 6.7±0.5 for the characteristic ratio of PE was also calculated. To investigate the role of a bulky side group in crystalline phases, wide angle X-ray diffraction experiments using a Hikosaka pressure cell were performed on P4MP1. Computer modelling, utilising the experimental data obtained, determined the structure of a disordered phase produced at room temperature and a new high pressure/high temperature phase. The disordered phase was found to be due to a collapse of the backbone combined with some disordering of the side chains

Optimal solutions for routing problems with profits

NARCIS (Netherlands)

Archetti, C.; Bianchessi, N.; Speranza, M. G.

2013-01-01

In this paper, we present a branch-and-price algorithm to solve two well-known vehicle routing problems with profits, the Capacitated Team Orienteering Problem and the Capacitated Profitable Tour Problem. A restricted master heuristic is applied at each node of the branch-and-bound tree in order to

An efficient method for generalized linear multiplicative programming problem with multiplicative constraints.

Science.gov (United States)

Zhao, Yingfeng; Liu, Sanyang

2016-01-01

We present a practical branch and bound algorithm for globally solving generalized linear multiplicative programming problem with multiplicative constraints. To solve the problem, a relaxation programming problem which is equivalent to a linear programming is proposed by utilizing a new two-phase relaxation technique. In the algorithm, lower and upper bounds are simultaneously obtained by solving some linear relaxation programming problems. Global convergence has been proved and results of some sample examples and a small random experiment show that the proposed algorithm is feasible and efficient.

Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons

KAUST Repository

Bae, Sang Won

2016-03-21

We establish tight bounds for beacon-based coverage problems. In particular, we show that $$\\\\lfloor \\\\frac{n}{6} \\ floor $$⌊n6⌋ beacons are always sufficient and sometimes necessary to cover a simple rectilinear polygon P with n vertices. When P is monotone and rectilinear, we prove that this bound becomes $$\\\\lfloor \\\\frac{n+4}{8} \\ floor $$⌊n+48⌋. We also present an optimal linear-time algorithm for computing the beacon kernel of P.

Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons

KAUST Repository

Bae, Sang Won; Shin, Chan-Su; Vigneron, Antoine E.

2016-01-01

We establish tight bounds for beacon-based coverage problems. In particular, we show that $$\\lfloor \\frac{n}{6} \\rfloor $$⌊n6⌋ beacons are always sufficient and sometimes necessary to cover a simple rectilinear polygon P with n vertices. When P is monotone and rectilinear, we prove that this bound becomes $$\\lfloor \\frac{n+4}{8} \\rfloor $$⌊n+48⌋. We also present an optimal linear-time algorithm for computing the beacon kernel of P.

Nonlinear Economic Model Predictive Control Strategy for Active Smart Buildings

DEFF Research Database (Denmark)

Santos, Rui Mirra; Zong, Yi; Sousa, Joao M. C.

2016-01-01

Nowadays, the development of advanced and innovative intelligent control techniques for energy management in buildings is a key issue within the smart grid topic. A nonlinear economic model predictive control (EMPC) scheme, based on the branch-and-bound tree search used as optimization algorithm ...... controller is shown very reliable keeping the comfort levels in the two considered seasons and shifting the load away from peak hours in order to achieve the desired flexible electricity consumption.......Nowadays, the development of advanced and innovative intelligent control techniques for energy management in buildings is a key issue within the smart grid topic. A nonlinear economic model predictive control (EMPC) scheme, based on the branch-and-bound tree search used as optimization algorithm...

Accurate branching ratio measurements in 23Na(p,γ)24Mg

International Nuclear Information System (INIS)

Boydell, S.G.; Sargood, D.G.

1975-01-01

The reaction 23 Na(p,γ) 24 Mg has been investigated in the proton energy range 0.3-1.75 MeV. Gamma ray spectra were measured for 22 resonances with Ge(Li) detectors which were carefully calibrated for relative peak efficiencies. Allowance was made for the effect of anisotropies in all the emitted γ-rays. The spectra have been analysed to give branching ratios for bound and unbound levels. (author)

DESIGN AND EXAMINATION OF ALGORITHMS FOR SOLVING THE KNAPSACK PROBLEM

Directory of Open Access Journals (Sweden)

S. Kantsedal

2015-07-01

Full Text Available The use of methods of branches and boundaries as well as the methods of dynamic programming at solving the problem of «knapsack» is grounded. The main concepts are expounded. The methods and algorithms development for solving the above specified problem are described. Recommendations on practical application of constructed algorithms based on their experimental investigation and carrying out charactheristics comparison are presented.

Z3str3: A String Solver with Theory-aware Branching

OpenAIRE

Berzish, Murphy; Zheng, Yunhui; Ganesh, Vijay

2017-01-01

We present a new string SMT solver, Z3str3, that is faster than its competitors Z3str2, Norn, CVC4, S3, and S3P over a majority of three industrial-strength benchmarks, namely Kaluza, PISA, and IBM AppScan. Z3str3 supports string equations, linear arithmetic over length function, and regular language membership predicate. The key algorithmic innovation behind the efficiency of Z3str3 is a technique we call theory-aware branching, wherein we modify Z3's branching heuristic to take into account...

Estimating the Probabilities of Low-Weight Differential and Linear Approximations on PRESENT-like Ciphers

DEFF Research Database (Denmark)

Abdelraheem, Mohamed Ahmed

2012-01-01

We use large but sparse correlation and transition-difference-probability submatrices to find the best linear and differential approximations respectively on PRESENT-like ciphers. This outperforms the branch and bound algorithm when the number of low-weight differential and linear characteristics...

Another view on the SSS* algorithm

NARCIS (Netherlands)

W.H.L.M. Pijls (Wim); A. de Bruin (Arie)

1990-01-01

textabstractA new version of the SSS* algorithm for searching game trees is presented. This algorithm is built around two recursive procedures. It finds the minimax value of a game tree by first establishing an upper bound to this value and then successively trying in a top down fashion to tighten

ROBUST CONTROL ALGORITHM FOR MULTIVARIABLE PLANTS WITH QUANTIZED OUTPUT

Directory of Open Access Journals (Sweden)

A. A. Margun

2017-01-01

Full Text Available The paper deals with robust output control algorithm for multivariable plants under disturbances. A plant is described by the system of linear differential equations with known relative degrees. Plant parameters are unknown but belong to the known closed bounded set. Plant state vector is unmeasured. Plant output is measured only via static quantizer. Control system algorithm is based on the high gain feedback method. Developed controller provides exponential convergence of tracking error to the bounded area. The area bounds depend on quantizer parameters and the value of external disturbances. Experimental approbation of the proposed control algorithm is performed with the use of Twin Rotor MIMO System laboratory bench. This bench is a helicopter like model with two degrees of freedom (pitch and yaw. DC motors are used as actuators. The output signals are measured via optical encoders. Mathematical model of laboratory bench is obtained. Proposed algorithm was compared with proportional - integral – differential controller in conditions of output quantization. Obtained results have confirmed the efficiency of proposed controller.

Optimal Fungal Space Searching Algorithms.

Science.gov (United States)

Asenova, Elitsa; Lin, Hsin-Yu; Fu, Eileen; Nicolau, Dan V; Nicolau, Dan V

2016-10-01

Previous experiments have shown that fungi use an efficient natural algorithm for searching the space available for their growth in micro-confined networks, e.g., mazes. This natural "master" algorithm, which comprises two "slave" sub-algorithms, i.e., collision-induced branching and directional memory, has been shown to be more efficient than alternatives, with one, or the other, or both sub-algorithms turned off. In contrast, the present contribution compares the performance of the fungal natural algorithm against several standard artificial homologues. It was found that the space-searching fungal algorithm consistently outperforms uninformed algorithms, such as Depth-First-Search (DFS). Furthermore, while the natural algorithm is inferior to informed ones, such as A*, this under-performance does not importantly increase with the increase of the size of the maze. These findings suggest that a systematic effort of harvesting the natural space searching algorithms used by microorganisms is warranted and possibly overdue. These natural algorithms, if efficient, can be reverse-engineered for graph and tree search strategies.

Closed form bound-state perturbation theory

Directory of Open Access Journals (Sweden)

Ollie J. Rose

1980-01-01

Full Text Available The perturbed Schrödinger eigenvalue problem for bound states is cast into integral form using Green's Functions. A systematic algorithm is developed and applied to the resulting equation giving rise to approximate solutions expressed as functions of the given perturbation parameter. As a by-product, convergence radii for the traditional Rayleigh-Schrödinger and Brillouin-Wigner perturbation theories emerge in a natural way.

A Faster Algorithm for Computing Straight Skeletons

KAUST Repository

Cheng, Siu-Wing

2014-09-01

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n (logn)logr) time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected O(n√h+1log2n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in O(n (logn) logr + r 4/3 + ε ) time for any ε > 0. On degenerate input, our time bound increases to O(n (logn) logr + r 17/11 + ε ).

A Faster Algorithm for Computing Straight Skeletons

KAUST Repository

Mencel, Liam A.

2014-05-06

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n (log n) log r) time. It improves on the previously best known algorithm for this reduction, which is randomised, and runs in expected O(n √(h+1) log² n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in O(n (log n) log r + r^(4/3 + ε)) time for any ε > 0. On degenerate input, our time bound increases to O(n (log n) log r + r^(17/11 + ε))

A Faster Algorithm for Computing Straight Skeletons

KAUST Repository

Cheng, Siu-Wing; Mencel, Liam A.; Vigneron, Antoine E.

2014-01-01

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph computation in O(n (logn)logr) time. It improves on the previously best known algorithm for this reduction, which is randomized, and runs in expected O(n√h+1log2n) time for a polygon with h holes. Using known motorcycle graph algorithms, our result yields improved time bounds for computing straight skeletons. In particular, we can compute the straight skeleton of a non-degenerate polygon in O(n (logn) logr + r 4/3 + ε ) time for any ε > 0. On degenerate input, our time bound increases to O(n (logn) logr + r 17/11 + ε ).

Clique Relaxations in Biological and Social Network Analysis Foundations and Algorithms

Science.gov (United States)

2015-10-26

NUMBER 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) Optimization and Discrete Mathematics Mathematics , Information and Life Sciences Air...Business Media, 2013, pp.149-174. J. Pattillo, Y. Wang, and S. Butenko. Approximating 2-cliques in unit disk graphs. Discrete Applied Mathematics 166 (2014...for developing effective combinatorial branch-and-bound strategies for detection of maximum clique relaxation structures. The concepts of weak heredity

A note on bound constraints handling for the IEEE CEC'05 benchmark function suite.

Science.gov (United States)

Liao, Tianjun; Molina, Daniel; de Oca, Marco A Montes; Stützle, Thomas

2014-01-01

The benchmark functions and some of the algorithms proposed for the special session on real parameter optimization of the 2005 IEEE Congress on Evolutionary Computation (CEC'05) have played and still play an important role in the assessment of the state of the art in continuous optimization. In this article, we show that if bound constraints are not enforced for the final reported solutions, state-of-the-art algorithms produce infeasible best candidate solutions for the majority of functions of the IEEE CEC'05 benchmark function suite. This occurs even though the optima of the CEC'05 functions are within the specified bounds. This phenomenon has important implications on algorithm comparisons, and therefore on algorithm designs. This article's goal is to draw the attention of the community to the fact that some authors might have drawn wrong conclusions from experiments using the CEC'05 problems.

Binar Sort: A Linear Generalized Sorting Algorithm

OpenAIRE

Gilreath, William F.

2008-01-01

Sorting is a common and ubiquitous activity for computers. It is not surprising that there exist a plethora of sorting algorithms. For all the sorting algorithms, it is an accepted performance limit that sorting algorithms are linearithmic or O(N lg N). The linearithmic lower bound in performance stems from the fact that the sorting algorithms use the ordering property of the data. The sorting algorithm uses comparison by the ordering property to arrange the data elements from an initial perm...

Ship Pipe Routing Design Using NSGA-II and Coevolutionary Algorithm

Directory of Open Access Journals (Sweden)

Wentie Niu

2016-01-01

Full Text Available Pipe route design plays a prominent role in ship design. Due to the complex configuration in layout space with numerous pipelines, diverse design constraints, and obstacles, it is a complicated and time-consuming process to obtain the optimal route of ship pipes. In this article, an optimized design method for branch pipe routing is proposed to improve design efficiency and to reduce human errors. By simplifying equipment and ship hull models and dividing workspace into three-dimensional grid cells, the mathematic model of layout space is constructed. Based on the proposed concept of pipe grading method, the optimization model of pipe routing is established. Then an optimization procedure is presented to deal with pipe route planning problem by combining maze algorithm (MA, nondominated sorting genetic algorithm II (NSGA-II, and cooperative coevolutionary nondominated sorting genetic algorithm II (CCNSGA-II. To improve the performance in genetic algorithm procedure, a fixed-length encoding method is presented based on improved maze algorithm and adaptive region strategy. Fuzzy set theory is employed to extract the best compromise pipeline from Pareto optimal solutions. Simulation test of branch pipe and design optimization of a fuel piping system were carried out to illustrate the design optimization procedure in detail and to verify the feasibility and effectiveness of the proposed methodology.

Filter Pattern Search Algorithms for Mixed Variable Constrained Optimization Problems

National Research Council Canada - National Science Library

Abramson, Mark A; Audet, Charles; Dennis, Jr, J. E

2004-01-01

.... This class combines and extends the Audet-Dennis Generalized Pattern Search (GPS) algorithms for bound constrained mixed variable optimization, and their GPS-filter algorithms for general nonlinear constraints...

Greedy algorithm with weights for decision tree construction

KAUST Repository

Moshkov, Mikhail

2010-01-01

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.

Greedy algorithm with weights for decision tree construction

KAUST Repository

Moshkov, Mikhail

2010-12-01

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.

Metaheurística algoritmo genético para solução de problemas de planejamento florestal com restrições de integridade Genetic algorithm metaheuristic to solve forest planning problem with integer constraints

Directory of Open Access Journals (Sweden)

Flávio Lopes Rodrigues

2004-04-01

Full Text Available Os objetivos deste trabalho foram desenvolver e testar um algoritmo genético (AG para a solução de problemas de gerenciamento florestal com restrições de integridade. O AG foi testado em quatro problemas, contendo entre 93 e 423 variáveis de decisão, sujeitos às restrições de singularidade, produção mínima e produção máxima, periodicamente. Todos os problemas tiveram como objetivo a maximização do valor presente líquido. O AG foi codificado em ambiente delphi 5.0 e os testes foram realizados em um microcomputador AMD K6II 500 MHZ, com memória RAM de 64 MB e disco rígido de 15GB. O desempenho do AG foi avaliado de acordo com as medidas de eficácia e eficiência. Os valores ou categorias dos parâmetros do AG foram testados e comparados quanto aos seus efeitos na eficácia do algoritmo. A seleção da melhor configuração de parâmetros foi feita com o teste L&O, a 1% de probabilidade, e as análises foram realizadas através de estatísticas descritivas. A melhor configuração de parâmetros propiciou ao AG eficácia média de 94,28%, valor mínimo de 90,01%, valor máximo de 98,48%, com coeficiente de variação de 2,08% do ótimo matemático, obtido pelo algoritmo exato branch and bound. Para o problema de maior porte, a eficiência do AG foi cinco vezes superior à eficiência do algoritmo exato branch and bound. O AG apresentou-se como uma abordagem bastante atrativa para solução de importantes problemas de gerenciamento florestal.The objectives of this work was to develop and test a Genetic Algorithm (GA to solve problems of forest management with integer constraints. GA was tested in five problems containing 93 - 423 decision variables, periodically subject to singularity constraints, minimum and maximum production. The problems had the objective of maximizing the net present value. GA was codified into delphi 5.0 language and the tests were performed in a microcomputer AMD K6II 500 MHZ, with RAM memory of 64 MB

A Branch and Cut algorithm for the container shipping network design problem

DEFF Research Database (Denmark)

Reinhardt, Line Blander; Kallehauge, Brian; Pisinger, David

The network design problem in liner shipping is of increasing importance in a strongly competitive market where potential cost reductions can influence market share and profits significantly. In this paper the network design and fleet assignment problems are combined into a mixed integer linear...... programming model minimizing the overall cost. To better reflect the real-life situation we take into account the cost of transhipment, a heterogeneous fleet, route dependant capacities, and butterfly routes. To the best of our knowledge it is the first time an exact solution method to the problem considers...... transhipment cost. The problem is solved with branch-and-cut using clover and transhipment inequalities. Computational results are reported for instances with up to 15 ports....

Bound states embedded into continuous spectrum as 'gathered' (compactified) scattering waves

International Nuclear Information System (INIS)

Zakhar'ev, B.N.; Chabanov, V.M.

1995-01-01

It is shown that states of continuous spectrum (the half-line case) can be considered as bound states normalized by unity but distributed on the infinite interval with vanishing density. Then the algorithms of shifting the range of primary localization of a chosen bound state in potential well of finite width appear to be applicable to scattering functions. The potential perturbations of the same type (but now on half-axis) concentrate the scattering wave in near vicinity of the origin, which leads to creation of bound state embedded into continuous spectrum. (author). 8 refs., 7 figs

Storage capacity of the Tilinglike Learning Algorithm

International Nuclear Information System (INIS)

Buhot, Arnaud; Gordon, Mirta B.

2001-01-01

The storage capacity of an incremental learning algorithm for the parity machine, the Tilinglike Learning Algorithm, is analytically determined in the limit of a large number of hidden perceptrons. Different learning rules for the simple perceptron are investigated. The usual Gardner-Derrida rule leads to a storage capacity close to the upper bound, which is independent of the learning algorithm considered

The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach - Technical Report

DEFF Research Database (Denmark)

Hansen, Anders Dohn; Kolind, Esben; Clausen, Jens

In this paper, we consider the Manpower Allocation Problem with Time Windows, Job-Teaming Constraints and a limited number of teams (m-MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks....... Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must initiate execution simultaneously. We present an IP-model for the problem, which is decomposed using Dantzig-Wolfe decomposition....... The problem is solved by column generation in a Branch-and-Price framework. Simultaneous execution of tasks is enforced by the branching scheme. To test the efficiency of the proposed algorithm, 12 realistic test instances are introduced. The algorithm is able to find the optimal solution in 11 of the test...

Distributed Large Independent Sets in One Round On Bounded-independence Graphs

OpenAIRE

Halldorsson , Magnus M.; Konrad , Christian

2015-01-01

International audience; We present a randomized one-round, single-bit messages, distributed algorithm for the maximum independent set problem in polynomially bounded-independence graphs with poly-logarithmic approximation factor. Bounded-independence graphs capture various models of wireless networks such as the unit disc graphs model and the quasi unit disc graphs model. For instance, on unit disc graphs, our achieved approximation ratio is O((log(n)/log(log(n)))^2).A starting point of our w...

A Branch-and-Price Framework for Railway Rolling Stock Rescheduling During Disruptions

DEFF Research Database (Denmark)

Haahr, Jørgen Thorlund; Lusby, Richard Martin; Larsen, Jesper

using column generation in a complete Branch-and-Price framework. In contrast to flow-based approaches our formulation is more easily extended to handle certain families of constraints, such as train unit maintenance restrictions. We benchmark the framework against real-life instances provided...... by the suburban railway operator in Copenhagen (DSB S-tog). In combination with a lower bound method we show that near-optimal solutions can be found within a few seconds during a disruption. In addition we show that framework is also able to find solution within a few minutes for non-disturbed timetables....

Reduced conservatism in stability robustness bounds by state transformation

Science.gov (United States)

Yedavalli, R. K.; Liang, Z.

1986-01-01

This note addresses the issue of 'conservatism' in the time domain stability robustness bounds obtained by the Liapunov approach. A state transformation is employed to improve the upper bounds on the linear time-varying perturbation of an asymptotically stable linear time-invariant system for robust stability. This improvement is due to the variance of the conservatism of the Liapunov approach with respect to the basis of the vector space in which the Liapunov function is constructed. Improved bounds are obtained, using a transformation, on elemental and vector norms of perturbations (i.e., structured perturbations) as well as on a matrix norm of perturbations (i.e., unstructured perturbations). For the case of a diagonal transformation, an algorithm is proposed to find the 'optimal' transformation. Several examples are presented to illustrate the proposed analysis.

Making the error-controlling algorithm of observable operator models constructive.

Science.gov (United States)

Zhao, Ming-Jie; Jaeger, Herbert; Thon, Michael

2009-12-01

Observable operator models (OOMs) are a class of models for stochastic processes that properly subsumes the class that can be modeled by finite-dimensional hidden Markov models (HMMs). One of the main advantages of OOMs over HMMs is that they admit asymptotically correct learning algorithms. A series of learning algorithms has been developed, with increasing computational and statistical efficiency, whose recent culmination was the error-controlling (EC) algorithm developed by the first author. The EC algorithm is an iterative, asymptotically correct algorithm that yields (and minimizes) an assured upper bound on the modeling error. The run time is faster by at least one order of magnitude than EM-based HMM learning algorithms and yields significantly more accurate models than the latter. Here we present a significant improvement of the EC algorithm: the constructive error-controlling (CEC) algorithm. CEC inherits from EC the main idea of minimizing an upper bound on the modeling error but is constructive where EC needs iterations. As a consequence, we obtain further gains in learning speed without loss in modeling accuracy.

Hydroxycinnamic acid bound arabinoxylans from millet brans-structural features and antioxidant activity.

Science.gov (United States)

Bijalwan, Vandana; Ali, Usman; Kesarwani, Atul Kumar; Yadav, Kamalendra; Mazumder, Koushik

2016-07-01

Hydroxycinnamic acid bound arabinoxylans (HCA-AXs) were extracted from brans of five Indian millet varieties and response surface methodology was used to optimize the extraction conditions. The optimal condition to obtain highest yield of millet HCA-AXs was determined as follows: time 61min, temperature 66°C, ratio of solvent to sample 12ml/g. Linkage analysis indicated that hydroxycinnamic acid bound arabinoxylan from kodo millet (KM-HCA-AX) contained comparatively low branched arabinoxylan consisting of 14.6% mono-substituted, 1.2% di-substituted and 41.2% un-substituted Xylp residues. The HPLC analysis of millet HCA-AXs showed significant variation in the content of three major bound hydroxycinnamic acids (caffeic, p-coumaric and ferulic acid). The antioxidant activity of millet HCA-AXs were evaluated using three in vitro assay methods (DPPH, FRAP and β-carotene linoleate emulsion assays) which suggested both phenolic acid composition and structural characteristics of arabinoxylans could be correlated to their antioxidant potential, the detailed structural analysis revealed that low substituted KM-HCA-AX exhibited relatively higher antioxidant activity compared to other medium and highly substituted HCA-AXs from finger (FM), proso (PM), barnyard (BM) and foxtail (FOXM) millet. Copyright © 2016. Published by Elsevier B.V.

On Solving Aircraft Conflict Avoidance Using Deterministic Global Optimization (sBB) Codes

OpenAIRE

Cafieri , Sonia; Messine , Frédéric; Touhami , Ahmed

2016-01-01

International audience; In this paper, some improvements of spatial Branch and Bound (sBB) algorithms are discussed to solve aircraft conflict avoidance problems formulated as MINLP. We propose a new quadratic convex relaxation technique based on affine arithmetic. Moreover, a branching strategy is also proposedfor the considered problem. Preliminary numerical results validates the proposed approach

Generic Lower Bounds for Root Extraction and Signature Schemes in General Groups

DEFF Research Database (Denmark)

Damgård, Ivan Bjerre; Koprowski, Maciej

2002-01-01

not use any special properties of the group at hand. We prove an exponential lower bound on the generic complexity of root extraction, even if the algorithm can choose the public exponent itself. In other words, both the standard and the strong RSA assumption are provably true w.r.t. generic algorithms...... it in RSA groups without the original restriction that the modulus must be a product of safe primes. It can also be implemented in class groups. In all cases, security follows from a well defined complexity assumption (the strong root assumption), without relying on random oracles, and the assumption...

Improved algorithms for approximate string matching (extended abstract

Directory of Open Access Journals (Sweden)

Papamichail Georgios

2009-01-01

Full Text Available Abstract Background The problem of approximate string matching is important in many different areas such as computational biology, text processing and pattern recognition. A great effort has been made to design efficient algorithms addressing several variants of the problem, including comparison of two strings, approximate pattern identification in a string or calculation of the longest common subsequence that two strings share. Results We designed an output sensitive algorithm solving the edit distance problem between two strings of lengths n and m respectively in time O((s - |n - m|·min(m, n, s + m + n and linear space, where s is the edit distance between the two strings. This worst-case time bound sets the quadratic factor of the algorithm independent of the longest string length and improves existing theoretical bounds for this problem. The implementation of our algorithm also excels in practice, especially in cases where the two strings compared differ significantly in length. Conclusion We have provided the design, analysis and implementation of a new algorithm for calculating the edit distance of two strings with both theoretical and practical implications. Source code of our algorithm is available online.

Bounds on the Capacity of ASK Molecular Communication Channels with ISI

OpenAIRE

Ghavami, Siavash; Adve, Raviraj; Lahouti, Farshad

2015-01-01

There are now several works on the use of the additive inverse Gaussian noise (AIGN) model for the random transit time in molecular communication~(MC) channels. The randomness invariably causes inter-symbol interference (ISI) in MC, an issue largely ignored or simplified. In this paper we derive an upper bound and two lower bounds for MC based on amplitude shift keying (ASK) in presence of ISI. The Blahut-Arimoto algorithm~(BAA) is modified to find the input distribution of transmitted symbol...

A subexponential lower bound for the Random Facet algorithm for Parity Games

DEFF Research Database (Denmark)

Friedmann, Oliver; Hansen, Thomas Dueholm; Zwick, Uri

2011-01-01

Parity Games form an intriguing family of infinite duration games whose solution is equivalent to the solution of important problems in automatic verification and automata theory. They also form a very natural subclass of Deterministic Mean Payoff Games, which in turn is a very natural subclass...... of turn-based Stochastic Mean Payoff Games. It is a major open problem whether these game families can be solved in polynomial time. The currently theoretically fastest algorithms for the solution of all these games are adaptations of the randomized algorithms of Kalai and of Matouˇsek, Sharir and Welzl...... for LP-type problems, an abstract generalization of linear programming. The expected running time of both algorithms is subexponential in the size of the game, i.e., 2O(√n log n), where n is the number of vertices in the game. We focus in this paper on the algorithm of Matouˇsek, Sharir and Welzl...

Delay Bounded Multi-Source Multicast in Software-Defined Networking

Directory of Open Access Journals (Sweden)

Thabo Semong

2018-01-01

Full Text Available Software-Defined Networking (SDN is the next generation network architecture with exciting application prospects. The control function in SDN is decoupled from the data forwarding plane, hence it provides a new centralized architecture with flexible network resource management. Although SDN is attracting much attention from both industry and research, its advantage over the traditional networks has not been fully utilized. Multicast is designed to deliver content to multiple destinations. The current traffic engineering in SDN focuses mainly on unicast, however, multicast can effectively reduce network resource consumption by serving multiple clients. This paper studies a novel delay-bounded multi-source multicast SDN problem, in which among the set of potential sources, we select a source to build the multicast-tree, under the constraint that the transmission delay for every destination is bounded. This problem is more difficult than the traditional Steiner minimum tree (SMT problem, since it needs to find a source from the set of all potential sources. We model the problem as a mixed-integer linear programming (MILP and prove its NP-Hardness. To solve the problem, a delay bounded multi-source (DBMS scheme is proposed, which includes a DBMS algorithm to build a minimum delay cost DBMS-Forest. Through a MATLAB experiment, we demonstrate that DBMS is significantly more efficient and outperforms other existing algorithms in the literature.

Search for the weak non-analog Fermi branch in the 42Sc ground state beta decay

International Nuclear Information System (INIS)

DelVecchio, R.M.; Daehnick, W.W.

1978-01-01

We have searched for the β-decay branch from the 4 2Sc ground state to the 1.837 MeV level in 4 2Ca. Since both states are J/sup π/ = 0 + , T = 1, this decay is an example of a non-analog Fermi decay which could occur by reason of some mixing of the analog ground states into the lowest excited 0 + state in both 4 2Sc and 4 2Ca. As a signal for this branch, we looked for a subsequent cascade γ ray with a Ge(Li) detector-rabbit arrangement. We found a branching ratio of (2.2 +- 1.7) x 10 - 5 relative to the superallowed ground state to ground state decay. Interpreted as an upper limit, this corresponds to a branching ratio - 5 at the 68% confidence level. This result is at the lower bound of what present theory can predict with a Coulomb force mixing calculation

A 1.375-approximation algorithm for sorting by transpositions.

Science.gov (United States)

Elias, Isaac; Hartman, Tzvika

2006-01-01

Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a 10-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper, we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: we improve the lower bound for the transposition diameter of the symmetric group and determine the exact transposition diameter of simple permutations.

An error bound estimate and convergence of the Nodal-LTS N solution in a rectangle

International Nuclear Information System (INIS)

Hauser, Eliete Biasotto; Pazos, Ruben Panta; Tullio de Vilhena, Marco

2005-01-01

In this work, we report the mathematical analysis concerning error bound estimate and convergence of the Nodal-LTS N solution in a rectangle. For such we present an efficient algorithm, called LTS N 2D-Diag solution for Cartesian geometry

A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Czech Academy of Sciences Publication Activity Database

Šíma, Jiří; Žák, Stanislav

-, subm. 2015 (2018) ISSN 0022-0000 R&D Projects: GA ČR GBP202/12/G061; GA ČR GAP202/10/1333 Institutional support: RVO:67985807 Keywords : derandomization * Hitting Set * read-once branching programs * bounded width Subject RIV: IN - Informatics, Computer Science Impact factor: 1.678, year: 2016

Spiral branches and star formation

International Nuclear Information System (INIS)

Zasov, A.V.

1974-01-01

Origin of spiral branches of galaxies and formation of stars in them are considered from the point of view of the theory of the gravitational gas condensation, one of comparatively young theories. Arguments are presented in favour of the stellar condensation theory. The concept of the star formation of gas is no longer a speculative hypothesis. This is a theory which assumes quantitative verification and explains qualitatively many facts observed. And still our knowledge on the nature of spiral branches is very poor. It still remains vague what processes give origin to spiral branches, why some galaxies have spirals and others have none. And shapes of spiral branches are diverse. Some cases are known when spiral branches spread outside boundaries of galaxies themselves. Such spirals arise exclusively in the region where there are two or some interacting galaxies. Only first steps have been made in the explanation of the galaxy spiral branches, and it is necessary to carry out new observations and new theoretical calculations

Communication Lower Bounds and Optimal Algorithms for Programs that Reference Arrays - Part 1

Science.gov (United States)

2013-05-14

that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it...by UC Discovery (award DIG07-10227), with additional support from ParLab affiliates National Instruments, Nokia , NVIDIA, Oracle, and Samsung, and...presents a number of examples showing why the assumptions of Theorem 4.1 are in fact necessary to obtain a lower bound. Section 4.5 looks at one of these

Fixman compensating potential for general branched molecules

Energy Technology Data Exchange (ETDEWEB)

Jain, Abhinandan, E-mail: Abhi.Jain@jpl.nasa.gov [Jet Propulsion Laboratory, California Institute of Technology, 4800 Oak Grove Drive, Pasadena, California 91109 (United States); Kandel, Saugat; Wagner, Jeffrey; Larsen, Adrien; Vaidehi, Nagarajan, E-mail: nvaidehi@coh.org [Division of Immunology, Beckman Research Institute of the City of Hope, Duarte, California 91010 (United States)

2013-12-28

The technique of constraining high frequency modes of molecular motion is an effective way to increase simulation time scale and improve conformational sampling in molecular dynamics simulations. However, it has been shown that constraints on higher frequency modes such as bond lengths and bond angles stiffen the molecular model, thereby introducing systematic biases in the statistical behavior of the simulations. Fixman proposed a compensating potential to remove such biases in the thermodynamic and kinetic properties calculated from dynamics simulations. Previous implementations of the Fixman potential have been limited to only short serial chain systems. In this paper, we present a spatial operator algebra based algorithm to calculate the Fixman potential and its gradient within constrained dynamics simulations for branched topology molecules of any size. Our numerical studies on molecules of increasing complexity validate our algorithm by demonstrating recovery of the dihedral angle probability distribution function for systems that range in complexity from serial chains to protein molecules. We observe that the Fixman compensating potential recovers the free energy surface of a serial chain polymer, thus annulling the biases caused by constraining the bond lengths and bond angles. The inclusion of Fixman potential entails only a modest increase in the computational cost in these simulations. We believe that this work represents the first instance where the Fixman potential has been used for general branched systems, and establishes the viability for its use in constrained dynamics simulations of proteins and other macromolecules.

Estimating the Propagation of Interdependent Cascading Outages with Multi-Type Branching Processes

Energy Technology Data Exchange (ETDEWEB)

Qi, Junjian; Ju, Wenyun; Sun, Kai

2016-01-01

In this paper, the multi-type branching process is applied to describe the statistics and interdependencies of line outages, the load shed, and isolated buses. The offspring mean matrix of the multi-type branching process is estimated by the Expectation Maximization (EM) algorithm and can quantify the extent of outage propagation. The joint distribution of two types of outages is estimated by the multi-type branching process via the Lagrange-Good inversion. The proposed model is tested with data generated by the AC OPA cascading simulations on the IEEE 118-bus system. The largest eigenvalues of the offspring mean matrix indicate that the system is closer to criticality when considering the interdependence of different types of outages. Compared with empirically estimating the joint distribution of the total outages, good estimate is obtained by using the multitype branching process with a much smaller number of cascades, thus greatly improving the efficiency. It is shown that the multitype branching process can effectively predict the distribution of the load shed and isolated buses and their conditional largest possible total outages even when there are no data of them.

Robust nonlinear model predictive control for nuclear power plants in load following operations with bounded xenon oscillations

International Nuclear Information System (INIS)

Eliasi, H.; Menhaj, M.B.; Davilu, H.

2011-01-01

Research highlights: → In this work, a robust nonlinear model predictive control algorithm is developed. → This algorithm is applied to control the power level for load following. → The state constraints are imposed on the predicted trajectory during optimization. → The xenon oscillations are the main constraint for the load following problem. → In this algorithm, xenon oscillations are bounded within acceptable limits. - Abstract: One of the important operations in nuclear power plants is load-following in which imbalance of axial power distribution induces xenon oscillations. These oscillations must be maintained within acceptable limits otherwise the nuclear power plant could become unstable. Therefore, bounded xenon oscillation considered to be a constraint for the load-following operation. In this paper, a robust nonlinear model predictive control for the load-following operation problem is proposed that ensures xenon oscillations are kept bounded within acceptable limits. The proposed controller uses constant axial offset (AO) strategy to maintain xenon oscillations to be bounded. The constant AO is a robust state constraint for load-following problem. The controller imposes restricted state constraints on the predicted trajectory during optimization which guarantees robust satisfaction of state constraints without restoring to a min-max optimization problem. Simulation results show that the proposed controller for the load-following operation is so effective so that the xenon oscillations kept bounded in the given region.

A Nonmonotone Trust Region Method for Nonlinear Programming with Simple Bound Constraints

International Nuclear Information System (INIS)

Chen, Z.-W.; Han, J.-Y.; Xu, D.-C.

2001-01-01

In this paper we propose a nonmonotone trust region algorithm for optimization with simple bound constraints. Under mild conditions, we prove the global convergence of the algorithm. For the monotone case it is also proved that the correct active set can be identified in a finite number of iterations if the strict complementarity slackness condition holds, and so the proposed algorithm reduces finally to an unconstrained minimization method in a finite number of iterations, allowing a fast asymptotic rate of convergence. Numerical experiments show that the method is efficient

An efficient algorithm for computing fixed length attractors based on bounded model checking in synchronous Boolean networks with biochemical applications.

Science.gov (United States)

Li, X Y; Yang, G W; Zheng, D S; Guo, W S; Hung, W N N

2015-04-28

Genetic regulatory networks are the key to understanding biochemical systems. One condition of the genetic regulatory network under different living environments can be modeled as a synchronous Boolean network. The attractors of these Boolean networks will help biologists to identify determinant and stable factors. Existing methods identify attractors based on a random initial state or the entire state simultaneously. They cannot identify the fixed length attractors directly. The complexity of including time increases exponentially with respect to the attractor number and length of attractors. This study used the bounded model checking to quickly locate fixed length attractors. Based on the SAT solver, we propose a new algorithm for efficiently computing the fixed length attractors, which is more suitable for large Boolean networks and numerous attractors' networks. After comparison using the tool BooleNet, empirical experiments involving biochemical systems demonstrated the feasibility and efficiency of our approach.

Accelerating rejection-based simulation of biochemical reactions with bounded acceptance probability

Energy Technology Data Exchange (ETDEWEB)

Thanh, Vo Hong, E-mail: vo@cosbi.eu [The Microsoft Research - University of Trento Centre for Computational and Systems Biology, Piazza Manifattura 1, Rovereto 38068 (Italy); Priami, Corrado, E-mail: priami@cosbi.eu [The Microsoft Research - University of Trento Centre for Computational and Systems Biology, Piazza Manifattura 1, Rovereto 38068 (Italy); Department of Mathematics, University of Trento, Trento (Italy); Zunino, Roberto, E-mail: roberto.zunino@unitn.it [Department of Mathematics, University of Trento, Trento (Italy)

2016-06-14

Stochastic simulation of large biochemical reaction networks is often computationally expensive due to the disparate reaction rates and high variability of population of chemical species. An approach to accelerate the simulation is to allow multiple reaction firings before performing update by assuming that reaction propensities are changing of a negligible amount during a time interval. Species with small population in the firings of fast reactions significantly affect both performance and accuracy of this simulation approach. It is even worse when these small population species are involved in a large number of reactions. We present in this paper a new approximate algorithm to cope with this problem. It is based on bounding the acceptance probability of a reaction selected by the exact rejection-based simulation algorithm, which employs propensity bounds of reactions and the rejection-based mechanism to select next reaction firings. The reaction is ensured to be selected to fire with an acceptance rate greater than a predefined probability in which the selection becomes exact if the probability is set to one. Our new algorithm improves the computational cost for selecting the next reaction firing and reduces the updating the propensities of reactions.

Heuristic approach to Satellite Range Scheduling with Bounds using Lagrangian Relaxation.

Energy Technology Data Exchange (ETDEWEB)

Brown, Nathanael J. K.; Arguello, Bryan; Nozick, Linda Karen; Xu, Ningxiong [Cornell

2017-03-01

This paper focuses on scheduling antennas to track satellites using a heuristic method. In order to validate the performance of the heuristic, bounds are developed using Lagrangian relaxation. The performance of the algorithm is established using several illustrative problems.

Formation control of robotic swarm using bounded artificial forces.

Science.gov (United States)

Qin, Long; Zha, Yabing; Yin, Quanjun; Peng, Yong

2013-01-01

Formation control of multirobot systems has drawn significant attention in the recent years. This paper presents a potential field control algorithm, navigating a swarm of robots into a predefined 2D shape while avoiding intermember collisions. The algorithm applies in both stationary and moving targets formation. We define the bounded artificial forces in the form of exponential functions, so that the behavior of the swarm drove by the forces can be adjusted via selecting proper control parameters. The theoretical analysis of the swarm behavior proves the stability and convergence properties of the algorithm. We further make certain modifications upon the forces to improve the robustness of the swarm behavior in the presence of realistic implementation considerations. The considerations include obstacle avoidance, local minima, and deformation of the shape. Finally, detailed simulation results validate the efficiency of the proposed algorithm, and the direction of possible futrue work is discussed in the conclusions.

A comparison between skeleton and bounding box models for falling direction recognition

Science.gov (United States)

Narupiyakul, Lalita; Srisrisawang, Nitikorn

2017-12-01

Falling is an injury that can lead to a serious medical condition in every range of the age of people. However, in the case of elderly, the risk of serious injury is much higher. Due to the fact that one way of preventing serious injury is to treat the fallen person as soon as possible, several works attempted to implement different algorithms to recognize the fall. Our work compares the performance of two models based on features extraction: (i) Body joint data (Skeleton Data) which are the joint's positions in 3 axes and (ii) Bounding box (Box-size Data) covering all body joints. Machine learning algorithms that were chosen are Decision Tree (DT), Naïve Bayes (NB), K-nearest neighbors (KNN), Linear discriminant analysis (LDA), Voting Classification (VC), and Gradient boosting (GB). The results illustrate that the models trained with Skeleton data are performed far better than those trained with Box-size data (with an average accuracy of 94-81% and 80-75%, respectively). KNN shows the best performance in both Body joint model and Bounding box model. In conclusion, KNN with Body joint model performs the best among the others.

A Branch-and-Price Algorithm for Two Multi-Compartment Vehicle Routing Problems

DEFF Research Database (Denmark)

Mirzaei, Samira; Wøhlk, Sanne

2017-01-01

by comparing the optimal costs of the two versions. Computational results are presented for instances with up to 100 customers and the algorithm can solve instances with up to 50 customers and 4 commodities to optimality. NOTE: An early version of the paper was made public on the website of the journal...

Extreme-Scale Algorithms & Software Resilience (EASIR) Architecture-Aware Algorithms for Scalable Performance and Resilience on Heterogeneous Architectures

Energy Technology Data Exchange (ETDEWEB)

Demmel, James W. [Univ. of California, Berkeley, CA (United States)

2017-09-14

This project addresses both communication-avoiding algorithms, and reproducible floating-point computation. Communication, i.e. moving data, either between levels of memory or processors over a network, is much more expensive per operation than arithmetic (measured in time or energy), so we seek algorithms that greatly reduce communication. We developed many new algorithms for both dense and sparse, and both direct and iterative linear algebra, attaining new communication lower bounds, and getting large speedups in many cases. We also extended this work in several ways: (1) We minimize writes separately from reads, since writes may be much more expensive than reads on emerging memory technologies, like Flash, sometimes doing asymptotically fewer writes than reads. (2) We extend the lower bounds and optimal algorithms to arbitrary algorithms that may be expressed as perfectly nested loops accessing arrays, where the array subscripts may be arbitrary affine functions of the loop indices (eg A(i), B(i,j+k, k+3*m-7, …) etc.). (3) We extend our communication-avoiding approach to some machine learning algorithms, such as support vector machines. This work has won a number of awards. We also address reproducible floating-point computation. We define reproducibility to mean getting bitwise identical results from multiple runs of the same program, perhaps with different hardware resources or other changes that should ideally not change the answer. Many users depend on reproducibility for debugging or correctness. However, dynamic scheduling of parallel computing resources, combined with nonassociativity of floating point addition, makes attaining reproducibility a challenge even for simple operations like summing a vector of numbers, or more complicated operations like the Basic Linear Algebra Subprograms (BLAS). We describe an algorithm that computes a reproducible sum of floating point numbers, independent of the order of summation. The algorithm depends only on a

Comparison of some classification algorithms based on deterministic and nondeterministic decision rules

KAUST Repository

Delimata, Paweł

2010-01-01

We discuss two, in a sense extreme, kinds of nondeterministic rules in decision tables. The first kind of rules, called as inhibitory rules, are blocking only one decision value (i.e., they have all but one decisions from all possible decisions on their right hand sides). Contrary to this, any rule of the second kind, called as a bounded nondeterministic rule, can have on the right hand side only a few decisions. We show that both kinds of rules can be used for improving the quality of classification. In the paper, two lazy classification algorithms of polynomial time complexity are considered. These algorithms are based on deterministic and inhibitory decision rules, but the direct generation of rules is not required. Instead of this, for any new object the considered algorithms extract from a given decision table efficiently some information about the set of rules. Next, this information is used by a decision-making procedure. The reported results of experiments show that the algorithms based on inhibitory decision rules are often better than those based on deterministic decision rules. We also present an application of bounded nondeterministic rules in construction of rule based classifiers. We include the results of experiments showing that by combining rule based classifiers based on minimal decision rules with bounded nondeterministic rules having confidence close to 1 and sufficiently large support, it is possible to improve the classification quality. © 2010 Springer-Verlag.

Subspace Barzilai-Borwein Gradient Method for Large-Scale Bound Constrained Optimization

International Nuclear Information System (INIS)

Xiao Yunhai; Hu Qingjie

2008-01-01

An active set subspace Barzilai-Borwein gradient algorithm for large-scale bound constrained optimization is proposed. The active sets are estimated by an identification technique. The search direction consists of two parts: some of the components are simply defined; the other components are determined by the Barzilai-Borwein gradient method. In this work, a nonmonotone line search strategy that guarantees global convergence is used. Preliminary numerical results show that the proposed method is promising, and competitive with the well-known method SPG on a subset of bound constrained problems from CUTEr collection

A simpler and elegant algorithm for computing fractal dimension in ...

Indian Academy of Sciences (India)

Chaotic systems are now frequently encountered in almost all branches of sciences. Dimension of such systems provides an important measure for easy characterization of dynamics of the systems. Conventional algorithms for computing dimension of such systems in higher dimensional state space face an unavoidable ...

Depth from Edge and Intensity Based Stereo.

Science.gov (United States)

1982-09-01

a Mars Viking vehicle, and a random dotted coffee jar. Assessment of the algorithm is a bit difficult: it uses a fairly simple control structure with...correspondences. This use of an evaluation function estimator allowed the introduction of the extensive pruning of a branch and bound algorithm. Even with it...Figure 3-6). This is the edge reversal constraint, and was integral to the pruning . As it happens, this same constraint is the key to the use of the

Randomized and quantum algorithms for solving initial-value problems in ordinary differential equations of order k

Directory of Open Access Journals (Sweden)

Maciej Goćwin

2008-01-01

Full Text Available The complexity of initial-value problems is well studied for systems of equations of first order. In this paper, we study the \\(\\varepsilon\\-complexity for initial-value problems for scalar equations of higher order. We consider two models of computation, the randomized model and the quantum model. We construct almost optimal algorithms adjusted to scalar equations of higher order, without passing to systems of first order equations. The analysis of these algorithms allows us to establish upper complexity bounds. We also show (almost matching lower complexity bounds. The \\(\\varepsilon\\-complexity in the randomized and quantum setting depends on the regularity of the right-hand side function, but is independent of the order of equation. Comparing the obtained bounds with results known in the deterministic case, we see that randomized algorithms give us a speed-up by \\(1/2\\, and quantum algorithms by \\(1\\ in the exponent. Hence, the speed-up does not depend on the order of equation, and is the same as for the systems of equations of first order. We also include results of some numerical experiments which confirm theoretical results.

Capacity Bounds and Mapping Design for Binary Symmetric Relay Channels

Directory of Open Access Journals (Sweden)

Majid Nasiri Khormuji

2012-12-01

Full Text Available Capacity bounds for a three-node binary symmetric relay channel with orthogonal components at the destination are studied. The cut-set upper bound and the rates achievable using decode-and-forward (DF, partial DF and compress-and-forward (CF relaying are first evaluated. Then relaying strategies with finite memory-length are considered. An efficient algorithm for optimizing the relay functions is presented. The Boolean Fourier transform is then employed to unveil the structure of the optimized mappings. Interestingly, the optimized relay functions exhibit a simple structure. Numerical results illustrate that the rates achieved using the optimized low-dimensional functions are either comparable to those achieved by CF or superior to those achieved by DF relaying. In particular, the optimized low-dimensional relaying scheme can improve on DF relaying when the quality of the source-relay link is worse than or comparable to that of other links.

Branching ratio and direct CP-violating rate asymmetry of the rare decays B →K*γand B→ργ

International Nuclear Information System (INIS)

Greub, C.; Simma, H.; Wyler, D.

1994-06-01

We calculate CP-violating rate asymmetries in the rare radiative decays B ± →K* ± γ and B ± →ρ ± γ. They arise because of the interference between leading-order penguin amplitudes and one-gluon corrections with absorptive phases, and provide unambiguous evidence for direct CP violation. Complementing earlier studies, we also investigate gluon exchange with the 'spectator' quark. The bound state effects in the exclusive matrix elements are taken into account by a covariant model, which yields a branching ratio BR(B→K*γ)=(4-5)x10 -5 in good agreement with the observed value. The bound state effects increase the CP asymmetry, which is of order 1% in the channel B→K*γ and 15% for B→ργ. (orig.)

Gradients in giant branch morphology in the core of 47 Tucanae

Science.gov (United States)

Bailyn, Charles D.

1994-01-01

I describe an algorithm which uses the high spatial resolution of the Hubble Space Telescope to complement the high spatial-to-noise, approximately symmetric point response function, relatively large spatial coverage, and standard filters available from ground based images of crowded fields. Applying this technique to the central regions of the globular cluster 47 Tucanae, I find that the morphology of the giant branch in the core is significantly different from that in more distant regions (r approximately equals 5 to 10 core radii) of the cluster. In particular, there appear to be fewer bright giants in the core, along with an enhanced `asymptotic giant branch' (AGB) sequence. Depletion of giants has been observed in the cores of other dense clusters, and may be due to `stripping' of large stars by stellar encounters and/or mass transfer in binary systems. Central concentrations of true asymptotic giant branch stars are not expected to result from dynamical processes; possibly some of these stars may be evolved blue stragglers.

Separation and Extension of Cover Inequalities for Conic Quadratic Knapsack Constraints with Generalized Upper Bounds

DEFF Research Database (Denmark)

Atamtürk, Alper; Muller, Laurent Flindt; Pisinger, David

2013-01-01

Motivated by addressing probabilistic 0-1 programs we study the conic quadratic knapsack polytope with generalized upper bound (GUB) constraints. In particular, we investigate separating and extending GUB cover inequalities. We show that, unlike in the linear case, determining whether a cover can...... be extended with a single variable is NP-hard. We describe and compare a number of exact and heuristic separation and extension algorithms which make use of the structure of the constraints. Computational experiments are performed for comparing the proposed separation and extension algorithms...

Bounded fractional diffusion in geological media: Definition and Lagrangian approximation

Science.gov (United States)

Zhang, Yong; Green, Christopher T.; LaBolle, Eric M.; Neupauer, Roseanna M.; Sun, HongGuang

2016-01-01

Spatiotemporal Fractional-Derivative Models (FDMs) have been increasingly used to simulate non-Fickian diffusion, but methods have not been available to define boundary conditions for FDMs in bounded domains. This study defines boundary conditions and then develops a Lagrangian solver to approximate bounded, one-dimensional fractional diffusion. Both the zero-value and non-zero-value Dirichlet, Neumann, and mixed Robin boundary conditions are defined, where the sign of Riemann-Liouville fractional derivative (capturing non-zero-value spatial-nonlocal boundary conditions with directional super-diffusion) remains consistent with the sign of the fractional-diffusive flux term in the FDMs. New Lagrangian schemes are then proposed to track solute particles moving in bounded domains, where the solutions are checked against analytical or Eularian solutions available for simplified FDMs. Numerical experiments show that the particle-tracking algorithm for non-Fickian diffusion differs from Fickian diffusion in relocating the particle position around the reflective boundary, likely due to the non-local and non-symmetric fractional diffusion. For a non-zero-value Neumann or Robin boundary, a source cell with a reflective face can be applied to define the release rate of random-walking particles at the specified flux boundary. Mathematical definitions of physically meaningful nonlocal boundaries combined with bounded Lagrangian solvers in this study may provide the only viable techniques at present to quantify the impact of boundaries on anomalous diffusion, expanding the applicability of FDMs from infinite do mains to those with any size and boundary conditions.

Stochastic bounded consensus of second-order multi-agent systems in noisy environment

International Nuclear Information System (INIS)

Ren Hong-Wei; Deng Fei-Qi

2017-01-01

This paper investigates the stochastic bounded consensus of leader-following second-order multi-agent systems in a noisy environment. It is assumed that each agent received the information of its neighbors corrupted by noises and time delays. Based on the graph theory, stochastic tools, and the Lyapunov function method, we derive the sufficient conditions under which the systems would reach stochastic bounded consensus in mean square with the protocol we designed. Finally, a numerical simulation is illustrated to check the effectiveness of the proposed algorithms. (paper)

Formation Control of Robotic Swarm Using Bounded Artificial Forces

Science.gov (United States)

Zha, Yabing; Peng, Yong

2013-01-01

Formation control of multirobot systems has drawn significant attention in the recent years. This paper presents a potential field control algorithm, navigating a swarm of robots into a predefined 2D shape while avoiding intermember collisions. The algorithm applies in both stationary and moving targets formation. We define the bounded artificial forces in the form of exponential functions, so that the behavior of the swarm drove by the forces can be adjusted via selecting proper control parameters. The theoretical analysis of the swarm behavior proves the stability and convergence properties of the algorithm. We further make certain modifications upon the forces to improve the robustness of the swarm behavior in the presence of realistic implementation considerations. The considerations include obstacle avoidance, local minima, and deformation of the shape. Finally, detailed simulation results validate the efficiency of the proposed algorithm, and the direction of possible futrue work is discussed in the conclusions. PMID:24453809

Formation Control of Robotic Swarm Using Bounded Artificial Forces

Directory of Open Access Journals (Sweden)

Long Qin

2013-01-01

Full Text Available Formation control of multirobot systems has drawn significant attention in the recent years. This paper presents a potential field control algorithm, navigating a swarm of robots into a predefined 2D shape while avoiding intermember collisions. The algorithm applies in both stationary and moving targets formation. We define the bounded artificial forces in the form of exponential functions, so that the behavior of the swarm drove by the forces can be adjusted via selecting proper control parameters. The theoretical analysis of the swarm behavior proves the stability and convergence properties of the algorithm. We further make certain modifications upon the forces to improve the robustness of the swarm behavior in the presence of realistic implementation considerations. The considerations include obstacle avoidance, local minima, and deformation of the shape. Finally, detailed simulation results validate the efficiency of the proposed algorithm, and the direction of possible futrue work is discussed in the conclusions.

A new hybrid imperialist competitive algorithm on data clustering

Indian Academy of Sciences (India)

Modified imperialist competitive algorithm; simulated annealing; ... Clustering is one of the unsupervised learning branches where a set of patterns, usually vectors ..... machine classification is based on design, operation, and/or purpose.

An error bound estimate and convergence of the Nodal-LTS {sub N} solution in a rectangle

Energy Technology Data Exchange (ETDEWEB)

Hauser, Eliete Biasotto [Faculty of Mathematics, PUCRS Av Ipiranga 6681, Building 15, Porto Alegre - RS 90619-900 (Brazil)]. E-mail: eliete@pucrs.br; Pazos, Ruben Panta [Department of Mathematics, UNISC Av Independencia, 2293, room 1301, Santa Cruz do Sul - RS 96815-900 (Brazil)]. E-mail: rpp@impa.br; Tullio de Vilhena, Marco [Graduate Program in Applied Mathematics, UFRGS Av Bento Goncalves 9500, Building 43-111, Porto Alegre - RS 91509-900 (Brazil)]. E-mail: vilhena@mat.ufrgs.br

2005-07-15

In this work, we report the mathematical analysis concerning error bound estimate and convergence of the Nodal-LTS {sub N} solution in a rectangle. For such we present an efficient algorithm, called LTS {sub N} 2D-Diag solution for Cartesian geometry.

Leakage detection and estimation algorithm for loss reduction in water piping networks

CSIR Research Space (South Africa)

Adedeji, KB

2017-10-01

Full Text Available the development of efficient algorithms for detecting leakage in water piping networks. Water distribution networks (WDNs) are disperse in nature with numerous number of nodes and branches. Consequently, identifying the segment(s) of the network and the exact...

Privacy preserving randomized gossip algorithms

KAUST Repository

Hanzely, Filip; Konečný , Jakub; Loizou, Nicolas; Richtarik, Peter; Grishchenko, Dmitry

2017-01-01

In this work we present three different randomized gossip algorithms for solving the average consensus problem while at the same time protecting the information about the initial private values stored at the nodes. We give iteration complexity bounds for all methods, and perform extensive numerical experiments.

Privacy preserving randomized gossip algorithms

KAUST Repository

Hanzely, Filip

2017-06-23

In this work we present three different randomized gossip algorithms for solving the average consensus problem while at the same time protecting the information about the initial private values stored at the nodes. We give iteration complexity bounds for all methods, and perform extensive numerical experiments.

CATEGORIES OF COMPUTER SYSTEMS ALGORITHMS

Directory of Open Access Journals (Sweden)

A. V. Poltavskiy

2015-01-01

Full Text Available Philosophy as a frame of reference on world around and as the first science is a fundamental basis, "roots" (R. Descartes for all branches of the scientific knowledge accumulated and applied in all fields of activity of a human being person. The theory of algorithms as one of the fundamental sections of mathematics, is also based on researches of the gnoseology conducting cognition of a true picture of the world of the buman being. From gnoseology and ontology positions as fundamental sections of philosophy modern innovative projects are inconceivable without development of programs,and algorithms.

A lower bound for the node, edge, and arc routing problem

DEFF Research Database (Denmark)

Bach, Lukas; Hasle, Geir; Wøhlk, Sanne

2013-01-01

The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004, although similar problems have been studied before. This problem, also called the Mixed Capacitated General Routing Problem (MCGRP), generalizes the classical Capacitated Vehicle Routing Problem (CVRP......), the Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It captures important aspects of real-life routing problems that were not adequately modeled in previous Vehicle Routing Problem (VRP) variants. The authors also proposed a memetic algorithm procedure and defined a set of test instances...... called the CBMix benchmark. The NEARP definition and investigation contribute to the development of rich VRPs. In this paper we present the first lower bound procedure for the NEARP. It is a further development of lower bounds for the CARP. We also define two novel sets of test instances to complement...

Error assessment of biogeochemical models by lower bound methods (NOMMA-1.0

Directory of Open Access Journals (Sweden)

V. Sauerland

2018-03-01

Full Text Available Biogeochemical models, capturing the major feedbacks of the pelagic ecosystem of the world ocean, are today often embedded into Earth system models which are increasingly used for decision making regarding climate policies. These models contain poorly constrained parameters (e.g., maximum phytoplankton growth rate, which are typically adjusted until the model shows reasonable behavior. Systematic approaches determine these parameters by minimizing the misfit between the model and observational data. In most common model approaches, however, the underlying functions mimicking the biogeochemical processes are nonlinear and non-convex. Thus, systematic optimization algorithms are likely to get trapped in local minima and might lead to non-optimal results. To judge the quality of an obtained parameter estimate, we propose determining a preferably large lower bound for the global optimum that is relatively easy to obtain and that will help to assess the quality of an optimum, generated by an optimization algorithm. Due to the unavoidable noise component in all observations, such a lower bound is typically larger than zero. We suggest deriving such lower bounds based on typical properties of biogeochemical models (e.g., a limited number of extremes and a bounded time derivative. We illustrate the applicability of the method with two real-world examples. The first example uses real-world observations of the Baltic Sea in a box model setup. The second example considers a three-dimensional coupled ocean circulation model in combination with satellite chlorophyll a.

Error assessment of biogeochemical models by lower bound methods (NOMMA-1.0)

Science.gov (United States)

Sauerland, Volkmar; Löptien, Ulrike; Leonhard, Claudine; Oschlies, Andreas; Srivastav, Anand

2018-03-01

Biogeochemical models, capturing the major feedbacks of the pelagic ecosystem of the world ocean, are today often embedded into Earth system models which are increasingly used for decision making regarding climate policies. These models contain poorly constrained parameters (e.g., maximum phytoplankton growth rate), which are typically adjusted until the model shows reasonable behavior. Systematic approaches determine these parameters by minimizing the misfit between the model and observational data. In most common model approaches, however, the underlying functions mimicking the biogeochemical processes are nonlinear and non-convex. Thus, systematic optimization algorithms are likely to get trapped in local minima and might lead to non-optimal results. To judge the quality of an obtained parameter estimate, we propose determining a preferably large lower bound for the global optimum that is relatively easy to obtain and that will help to assess the quality of an optimum, generated by an optimization algorithm. Due to the unavoidable noise component in all observations, such a lower bound is typically larger than zero. We suggest deriving such lower bounds based on typical properties of biogeochemical models (e.g., a limited number of extremes and a bounded time derivative). We illustrate the applicability of the method with two real-world examples. The first example uses real-world observations of the Baltic Sea in a box model setup. The second example considers a three-dimensional coupled ocean circulation model in combination with satellite chlorophyll a.

Branches of the Facial Artery.

Science.gov (United States)

Hwang, Kun; Lee, Geun In; Park, Hye Jin

2015-06-01

The aim of this study is to review the name of the branches, to review the classification of the branching pattern, and to clarify a presence percentage of each branch of the facial artery, systematically. In a PubMed search, the search terms "facial," AND "artery," AND "classification OR variant OR pattern" were used. The IBM SPSS Statistics 20 system was used for statistical analysis. Among the 500 titles, 18 articles were selected and reviewed systematically. Most of the articles focused on "classification" according to the "terminal branch." Several authors classified the facial artery according to their terminal branches. Most of them, however, did not describe the definition of "terminal branch." There were confusions within the classifications. When the inferior labial artery was absent, 3 different types were used. The "alar branch" or "nasal branch" was used instead of the "lateral nasal branch." The angular branch was used to refer to several different branches. The presence as a percentage of each branch according to the branches in Gray's Anatomy (premasseteric, inferior labial, superior labial, lateral nasal, and angular) varied. No branch was used with 100% consistency. The superior labial branch was most frequently cited (95.7%, 382 arteries in 399 hemifaces). The angular branch (53.9%, 219 arteries in 406 hemifaces) and the premasseteric branch were least frequently cited (53.8%, 43 arteries in 80 hemifaces). There were significant differences among each of the 5 branches (P < 0.05) except between the angular branch and the premasseteric branch and between the superior labial branch and the inferior labial branch. The authors believe identifying the presence percentage of each branch will be helpful for surgical procedures.

The bounds of feasible space on constrained nonconvex quadratic programming

Science.gov (United States)

Zhu, Jinghao

2008-03-01

This paper presents a method to estimate the bounds of the radius of the feasible space for a class of constrained nonconvex quadratic programmingsE Results show that one may compute a bound of the radius of the feasible space by a linear programming which is known to be a P-problem [N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373-395]. It is proposed that one applies this method for using the canonical dual transformation [D.Y. Gao, Canonical duality theory and solutions to constrained nonconvex quadratic programming, J. Global Optimization 29 (2004) 377-399] for solving a standard quadratic programming problem.

Characterization of the Diameter, branch angle and longevity of axial branches of Nothofagusobliqua

Directory of Open Access Journals (Sweden)

Patricio Corvalán Vera

2017-08-01

Full Text Available The lack of knowledge about grow dynamics of the living tree crown of Nothofagusobliqua secondary growth forests strongly limits the objective formulation of silvicultural schemes oriented to the industrial production of high quality wood. Therefore, in this work, we described basic relationships between tree size, age and angle branches insertion and the crown. Considering a sample data of 59 dominant trees, distributed in different age conditions, we applied a combined analysis technique of stem analysis, steam taper analysis and thickest branch measurement in each decile of the total height. This approach allowed us to determine that there is a significant relationship between the steam diameter, the angle insertion and the age of the branch, as well as the size and age of the trees. Also, the thicker branches tend to have lower insertion angles, to be older, to be located at lower relative heights and to be located in larger diameter sections. Taking into consideration these relationships, it is possible to build new predicted branch models as tools for the development of silvicultural schemes to suit different log grade.

Quivers of Bound Path Algebras and Bound Path Coalgebras

Directory of Open Access Journals (Sweden)

Dr. Intan Muchtadi

2010-09-01

Full Text Available bras and coalgebras can be represented as quiver (directed graph, and from quiver we can construct algebras and coalgebras called path algebras and path coalgebras. In this paper we show that the quiver of a bound path coalgebra (resp. algebra is the dual quiver of its bound path algebra (resp. coalgebra.

Learning theory of distributed spectral algorithms

International Nuclear Information System (INIS)

Guo, Zheng-Chu; Lin, Shao-Bo; Zhou, Ding-Xuan

2017-01-01

Spectral algorithms have been widely used and studied in learning theory and inverse problems. This paper is concerned with distributed spectral algorithms, for handling big data, based on a divide-and-conquer approach. We present a learning theory for these distributed kernel-based learning algorithms in a regression framework including nice error bounds and optimal minimax learning rates achieved by means of a novel integral operator approach and a second order decomposition of inverse operators. Our quantitative estimates are given in terms of regularity of the regression function, effective dimension of the reproducing kernel Hilbert space, and qualification of the filter function of the spectral algorithm. They do not need any eigenfunction or noise conditions and are better than the existing results even for the classical family of spectral algorithms. (paper)

An algorithmic decomposition of claw-free graphs leading to an O(n^3) algorithm for the weighted stable set problem

OpenAIRE

Faenza, Y.; Oriolo, G.; Stauffer, G.

2011-01-01

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also intioduced in the present paper. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour, our decomposition theorem is, on the other hand, algorithmic, i.e. it is ...

RELAXATION HEURISTICS FOR THE SET COVERING PROBLEM

OpenAIRE

Umetani, Shunji; Yagiura, Mutsunori; 柳浦, 睦憲

2007-01-01

The set covering problem (SCP) is one of representative combinatorial optimization problems, which has many practical applications. The continuous development of mathematical programming has derived a number of impressive heuristic algorithms as well as exact branch-and-bound algorithms, which can solve huge SCP instances of bus, railway and airline crew scheduling problems. We survey heuristic algorithms for SCP focusing mainly on contributions of mathematical programming techniques to heuri...

Methods for optimizing over the efficient and weakly efficient sets of an affine fractional vector optimization program

DEFF Research Database (Denmark)

Le, T.H.A.; Pham, D. T.; Canh, Nam Nguyen

2010-01-01

Both the efficient and weakly efficient sets of an affine fractional vector optimization problem, in general, are neither convex nor given explicitly. Optimization problems over one of these sets are thus nonconvex. We propose two methods for optimizing a real-valued function over the efficient...... and weakly efficient sets of an affine fractional vector optimization problem. The first method is a local one. By using a regularization function, we reformulate the problem into a standard smooth mathematical programming problem that allows applying available methods for smooth programming. In case...... the objective function is linear, we have investigated a global algorithm based upon a branch-and-bound procedure. The algorithm uses Lagrangian bound coupling with a simplicial bisection in the criteria space. Preliminary computational results show that the global algorithm is promising....

Robust Branch-Cut-and-Price for the Capacitated Minimum Spanning Tree Problem over a Large Extended Formulation

DEFF Research Database (Denmark)

Uchoa, Eduardo; Fukasawa, Ricardo; Lysgaard, Jens

This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to q-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence problem in order to make it solvable in pseudo......-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. Moreover, a novel feature is introduced in such kind of algorithms. Powerful new cuts expressed over a very large set of variables could be added, without increasing the complexity of the pricing subproblem...

Automated Detection of Branch Shaking Locations for Robotic Cherry Harvesting Using Machine Vision

Directory of Open Access Journals (Sweden)

Suraj Amatya

2017-10-01

Full Text Available Automation in cherry harvesting is essential to reduce the demand for seasonal labor for cherry picking and reduce the cost of production. The mechanical shaking of tree branches is one of the widely studied and used techniques for harvesting small tree fruit crops like cherries. To automate the branch shaking operation, different methods of detecting branches and cherries in full foliage canopies of the cherry tree have been developed previously. The next step in this process is the localization of shaking positions in the detected tree branches for mechanical shaking. In this study, a method of locating shaking positions for automated cherry harvesting was developed based on branch and cherry pixel locations determined using RGB images and 3D camera images. First, branch and cherry regions were located in 2D RGB images. Depth information provided by a 3D camera was then mapped on to the RGB images using a standard stereo calibration method. The overall root mean square error in estimating the distance to desired shaking points was 0.064 m. Cherry trees trained in two different canopy architectures, Y-trellis and vertical trellis systems, were used in this study. Harvesting testing was carried out by shaking tree branches at the locations selected by the algorithm. For the Y-trellis system, the maximum fruit removal efficiency of 92.9% was achieved using up to five shaking events per branch. However, maximum fruit removal efficiency for the vertical trellis system was 86.6% with up to four shakings per branch. However, it was found that only three shakings per branch would achieve a fruit removal percentage of 92.3% and 86.4% in Y and vertical trellis systems respectively.

Pair- ${v}$ -SVR: A Novel and Efficient Pairing nu-Support Vector Regression Algorithm.

Science.gov (United States)

Hao, Pei-Yi

This paper proposes a novel and efficient pairing nu-support vector regression (pair--SVR) algorithm that combines successfully the superior advantages of twin support vector regression (TSVR) and classical -SVR algorithms. In spirit of TSVR, the proposed pair--SVR solves two quadratic programming problems (QPPs) of smaller size rather than a single larger QPP, and thus has faster learning speed than classical -SVR. The significant advantage of our pair--SVR over TSVR is the improvement in the prediction speed and generalization ability by introducing the concepts of the insensitive zone and the regularization term that embodies the essence of statistical learning theory. Moreover, pair--SVR has additional advantage of using parameter for controlling the bounds on fractions of SVs and errors. Furthermore, the upper bound and lower bound functions of the regression model estimated by pair--SVR capture well the characteristics of data distributions, thus facilitating automatic estimation of the conditional mean and predictive variance simultaneously. This may be useful in many cases, especially when the noise is heteroscedastic and depends strongly on the input values. The experimental results validate the superiority of our pair--SVR in both training/prediction speed and generalization ability.This paper proposes a novel and efficient pairing nu-support vector regression (pair--SVR) algorithm that combines successfully the superior advantages of twin support vector regression (TSVR) and classical -SVR algorithms. In spirit of TSVR, the proposed pair--SVR solves two quadratic programming problems (QPPs) of smaller size rather than a single larger QPP, and thus has faster learning speed than classical -SVR. The significant advantage of our pair--SVR over TSVR is the improvement in the prediction speed and generalization ability by introducing the concepts of the insensitive zone and the regularization term that embodies the essence of statistical learning theory

Pre-emptive resource-constrained multimode project scheduling using genetic algorithm: A dynamic forward approach

Directory of Open Access Journals (Sweden)

Aidin Delgoshaei

2016-09-01

Full Text Available Purpose: The issue resource over-allocating is a big concern for project engineers in the process of scheduling project activities. Resource over-allocating drawback is frequently seen after scheduling of a project in practice which causes a schedule to be useless. Modifying an over-allocated schedule is very complicated and needs a lot of efforts and time. In this paper, a new and fast tracking method is proposed to schedule large scale projects which can help project engineers to schedule the project rapidly and with more confidence. Design/methodology/approach: In this article, a forward approach for maximizing net present value (NPV in multi-mode resource constrained project scheduling problem while assuming discounted positive cash flows (MRCPSP-DCF is proposed. The progress payment method is used and all resources are considered as pre-emptible. The proposed approach maximizes NPV using unscheduled resources through resource calendar in forward mode. For this purpose, a Genetic Algorithm is applied to solve. Findings: The findings show that the proposed method is an effective way to maximize NPV in MRCPSP-DCF problems while activity splitting is allowed. The proposed algorithm is very fast and can schedule experimental cases with 1000 variables and 100 resources in few seconds. The results are then compared with branch and bound method and simulated annealing algorithm and it is found the proposed genetic algorithm can provide results with better quality. Then algorithm is then applied for scheduling a hospital in practice. Originality/value: The method can be used alone or as a macro in Microsoft Office Project® Software to schedule MRCPSP-DCF problems or to modify resource over-allocated activities after scheduling a project. This can help project engineers to schedule project activities rapidly with more accuracy in practice.

Computing a Non-trivial Lower Bound on the Joint Entropy between Two Images

Energy Technology Data Exchange (ETDEWEB)

Perumalla, Kalyan S. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States)

2017-03-01

In this report, a non-trivial lower bound on the joint entropy of two non-identical images is developed, which is greater than the individual entropies of the images. The lower bound is the least joint entropy possible among all pairs of images that have the same histograms as those of the given images. New algorithms are presented to compute the joint entropy lower bound with a computation time proportional to S log S where S is the number of histogram bins of the images. This is faster than the traditional methods of computing the exact joint entropy with a computation time that is quadratic in S .

Crane Double Cycling in Container Ports: Algorithms, Evaluation, and Planning

OpenAIRE

Goodchild, Anne Victoria

2005-01-01

Loading ships as they are unloaded (double-cycling) can improve the efficiency of a quay crane and container port. This dissertation describes the double-cycling problem, and presents solution algorithms and simple formulae to estimate benefits. In Chapter 2 we focus on reducing the number of operations necessary to turn around a ship. First an intuitive lower bound is developed. We then present a greedy algorithm that was developed based on the physical properties of the problem and yields a...

Efficiency of free-energy calculations of spin lattices by spectral quantum algorithms

International Nuclear Information System (INIS)

Master, Cyrus P.; Yamaguchi, Fumiko; Yamamoto, Yoshihisa

2003-01-01

Ensemble quantum algorithms are well suited to calculate estimates of the energy spectra for spin-lattice systems. Based on the phase estimation algorithm, these algorithms efficiently estimate discrete Fourier coefficients of the density of states. Their efficiency in calculating the free energy per spin of general spin lattices to bounded error is examined. We find that the number of Fourier components required to bound the error in the free energy due to the broadening of the density of states scales polynomially with the number of spins in the lattice. However, the precision with which the Fourier components must be calculated is found to be an exponential function of the system size

Upper and lower bounds on the set of recoverable strains and on effective energies in cubic-to-monoclinic martensitic phase transformations

Directory of Open Access Journals (Sweden)

Schlömerkemper Anja

2015-01-01

Full Text Available A major open problem in the mathematical analysis of martensitic phase transformations is the derivation of explicit formulae for the set of recoverable strains and for the relaxed energy of the system. These are governed by the mathematical notion of quasiconvexity. Here we focus on bounds on these quasiconvex hulls and envelopes in the setting of geometrically-linear elasticity. Firstly, we will present mathematical results on triples of transformation strains. This yields further insight into the quasiconvex hull of the twelve transformation strains in cubic-to-monoclinic phase transformations. Secondly, we consider bounds on the energy of such materials based on the so-called energy of mixing thus obtaining a lamination upper bound on the quasiconvex envelope of the energy. Here we present a new algorithm that yields improved upper bounds and allows us to relate numerical results for the lamination upper bound on the energy with theoretical inner bounds on the quasiconvex hull of triples of transformation strains.

Mining Branching Rules from Past Survey Data with an Illustration Using a Geriatric Assessment Survey for Older Adults with Cancer

Directory of Open Access Journals (Sweden)

Daniel R. Jeske

2016-05-01

Full Text Available We construct a fast data mining algorithm that can be used to identify high-frequency response patterns in historical surveys. Identification of these patterns leads to the derivation of question branching rules that shorten the time required to complete a survey. The data mining algorithm allows the user to control the error rate that is incurred through the use of implied answers that go along with each branching rule. The context considered is binary response questions, which can be obtained from multi-level response questions through dichotomization. The algorithm is illustrated by the analysis of four sections of a geriatric assessment survey used by oncologists. Reductions in the number of questions that need to be asked in these four sections range from 33% to 54%.

Semioptimal practicable algorithmic cooling

International Nuclear Information System (INIS)

Elias, Yuval; Mor, Tal; Weinstein, Yossi

2011-01-01

Algorithmic cooling (AC) of spins applies entropy manipulation algorithms in open spin systems in order to cool spins far beyond Shannon's entropy bound. Algorithmic cooling of nuclear spins was demonstrated experimentally and may contribute to nuclear magnetic resonance spectroscopy. Several cooling algorithms were suggested in recent years, including practicable algorithmic cooling (PAC) and exhaustive AC. Practicable algorithms have simple implementations, yet their level of cooling is far from optimal; exhaustive algorithms, on the other hand, cool much better, and some even reach (asymptotically) an optimal level of cooling, but they are not practicable. We introduce here semioptimal practicable AC (SOPAC), wherein a few cycles (typically two to six) are performed at each recursive level. Two classes of SOPAC algorithms are proposed and analyzed. Both attain cooling levels significantly better than PAC and are much more efficient than the exhaustive algorithms. These algorithms are shown to bridge the gap between PAC and exhaustive AC. In addition, we calculated the number of spins required by SOPAC in order to purify qubits for quantum computation. As few as 12 and 7 spins are required (in an ideal scenario) to yield a mildly pure spin (60% polarized) from initial polarizations of 1% and 10%, respectively. In the latter case, about five more spins are sufficient to produce a highly pure spin (99.99% polarized), which could be relevant for fault-tolerant quantum computing.

Efficient Multi-Valued Bounded Model Checking for LTL over Quasi-Boolean Algebras

Science.gov (United States)

Andrade, Jefferson O.; Kameyama, Yukiyoshi

Multi-valued Model Checking extends classical, two-valued model checking to multi-valued logic such as Quasi-Boolean logic. The added expressivity is useful in dealing with such concepts as incompleteness and uncertainty in target systems, while it comes with the cost of time and space. Chechik and others proposed an efficient reduction from multi-valued model checking problems to two-valued ones, but to the authors' knowledge, no study was done for multi-valued bounded model checking. In this paper, we propose a novel, efficient algorithm for multi-valued bounded model checking. A notable feature of our algorithm is that it is not based on reduction of multi-values into two-values; instead, it generates a single formula which represents multi-valuedness by a suitable encoding, and asks a standard SAT solver to check its satisfiability. Our experimental results show a significant improvement in the number of variables and clauses and also in execution time compared with the reduction-based one.

Branched polynomial covering maps

DEFF Research Database (Denmark)

Hansen, Vagn Lundsgaard

2002-01-01

A Weierstrass polynomial with multiple roots in certain points leads to a branched covering map. With this as the guiding example, we formally define and study the notion of a branched polynomial covering map. We shall prove that many finite covering maps are polynomial outside a discrete branch ...... set. Particular studies are made of branched polynomial covering maps arising from Riemann surfaces and from knots in the 3-sphere. (C) 2001 Elsevier Science B.V. All rights reserved.......A Weierstrass polynomial with multiple roots in certain points leads to a branched covering map. With this as the guiding example, we formally define and study the notion of a branched polynomial covering map. We shall prove that many finite covering maps are polynomial outside a discrete branch...

78 FR 18326 - Agency Information Collection Activities; Comment Request; Upward Bound and Upward Bound Math...

Science.gov (United States)

2013-03-26

...; Comment Request; Upward Bound and Upward Bound Math Science Annual Performance Report AGENCY: The Office... considered public records. Title of Collection: Upward Bound and Upward Bound Math Science Annual Performance...) and Upward Bound Math and Science (UBMS) Programs. The Department is requesting a new APR because of...

Upper Bounds on the Number of Errors Corrected by the Koetter–Vardy Algorithm

DEFF Research Database (Denmark)

Justesen, Jørn

2007-01-01

By introducing a few simplifying assumptions we derive a simple condition for successful decoding using the Koetter-Vardy algorithm for soft-decision decoding of Reed-Solomon codes. We show that the algorithm has a significant advantage over hard decision decoding when the code rate is low, when ...

Analysis of Known Linear Distributed Average Consensus Algorithms on Cycles and Paths

Directory of Open Access Journals (Sweden)

Jesús Gutiérrez-Gutiérrez

2018-03-01

Full Text Available In this paper, we compare six known linear distributed average consensus algorithms on a sensor network in terms of convergence time (and therefore, in terms of the number of transmissions required. The selected network topologies for the analysis (comparison are the cycle and the path. Specifically, in the present paper, we compute closed-form expressions for the convergence time of four known deterministic algorithms and closed-form bounds for the convergence time of two known randomized algorithms on cycles and paths. Moreover, we also compute a closed-form expression for the convergence time of the fastest deterministic algorithm considered on grids.

The interplay of intrinsic and extrinsic bounded noises in biomolecular networks.

Directory of Open Access Journals (Sweden)

Giulio Caravagna

Full Text Available After being considered as a nuisance to be filtered out, it became recently clear that biochemical noise plays a complex role, often fully functional, for a biomolecular network. The influence of intrinsic and extrinsic noises on biomolecular networks has intensively been investigated in last ten years, though contributions on the co-presence of both are sparse. Extrinsic noise is usually modeled as an unbounded white or colored gaussian stochastic process, even though realistic stochastic perturbations are clearly bounded. In this paper we consider Gillespie-like stochastic models of nonlinear networks, i.e. the intrinsic noise, where the model jump rates are affected by colored bounded extrinsic noises synthesized by a suitable biochemical state-dependent Langevin system. These systems are described by a master equation, and a simulation algorithm to analyze them is derived. This new modeling paradigm should enlarge the class of systems amenable at modeling. We investigated the influence of both amplitude and autocorrelation time of a extrinsic Sine-Wiener noise on: (i the Michaelis-Menten approximation of noisy enzymatic reactions, which we show to be applicable also in co-presence of both intrinsic and extrinsic noise, (ii a model of enzymatic futile cycle and (iii a genetic toggle switch. In (ii and (iii we show that the presence of a bounded extrinsic noise induces qualitative modifications in the probability densities of the involved chemicals, where new modes emerge, thus suggesting the possible functional role of bounded noises.

The interplay of intrinsic and extrinsic bounded noises in biomolecular networks.

Science.gov (United States)

Caravagna, Giulio; Mauri, Giancarlo; d'Onofrio, Alberto

2013-01-01

After being considered as a nuisance to be filtered out, it became recently clear that biochemical noise plays a complex role, often fully functional, for a biomolecular network. The influence of intrinsic and extrinsic noises on biomolecular networks has intensively been investigated in last ten years, though contributions on the co-presence of both are sparse. Extrinsic noise is usually modeled as an unbounded white or colored gaussian stochastic process, even though realistic stochastic perturbations are clearly bounded. In this paper we consider Gillespie-like stochastic models of nonlinear networks, i.e. the intrinsic noise, where the model jump rates are affected by colored bounded extrinsic noises synthesized by a suitable biochemical state-dependent Langevin system. These systems are described by a master equation, and a simulation algorithm to analyze them is derived. This new modeling paradigm should enlarge the class of systems amenable at modeling. We investigated the influence of both amplitude and autocorrelation time of a extrinsic Sine-Wiener noise on: (i) the Michaelis-Menten approximation of noisy enzymatic reactions, which we show to be applicable also in co-presence of both intrinsic and extrinsic noise, (ii) a model of enzymatic futile cycle and (iii) a genetic toggle switch. In (ii) and (iii) we show that the presence of a bounded extrinsic noise induces qualitative modifications in the probability densities of the involved chemicals, where new modes emerge, thus suggesting the possible functional role of bounded noises.

Discrete optimization

CERN Document Server

Parker, R Gary

1988-01-01

This book treats the fundamental issues and algorithmic strategies emerging as the core of the discipline of discrete optimization in a comprehensive and rigorous fashion. Following an introductory chapter on computational complexity, the basic algorithmic results for the two major models of polynomial algorithms are introduced--models using matroids and linear programming. Further chapters treat the major non-polynomial algorithms: branch-and-bound and cutting planes. The text concludes with a chapter on heuristic algorithms.Several appendixes are included which review the fundamental ideas o

Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation

Science.gov (United States)

Hamane, Ryoso; Itoh, Toshiya

When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. If the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j∈C wishes to buy a set ej⊆V of items and assigns valuation w(ej)≥0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i. e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.

Simulation of quantum systems with random walks: A new algorithm for charged systems

International Nuclear Information System (INIS)

Ceperley, D.

1983-01-01

Random walks with branching have been used to calculate exact properties of the ground state of quantum many-body systems. In this paper, a more general Green's function identity is derived which relates the potential energy, a trial wavefunction, and a trial density matrix to the rules of a branched random walk. It is shown that an efficient algorithm requires a good trial wavefunction, a good trial density matrix, and a good sampling of this density matrix. An accurate density matrix is constructed for Coulomb systems using the path integral formula. The random walks from this new algorithm diffuse through phase space an order of magnitude faster than the previous Green's Function Monte Carlo method. In contrast to the simple diffusion Monte Carlo algorithm, it is exact method. Representative results are presented for several molecules

Linear Programming, the Simplex Algorithm and Simple Polytopes

Directory of Open Access Journals (Sweden)

Das Bhusan

2010-09-01

Full Text Available In the first part of the paper we survey some far reaching applications of the basis facts of linear programming to the combinatorial theory of simple polytopes. In the second part we discuss some recent developments concurring the simplex algorithm. We describe sub-exponential randomized pivot roles and upper bounds on the diameter of graphs of polytopes.

Stochastic integration of the Bethe-Salpeter equation for two bound fermions

International Nuclear Information System (INIS)

Salomon, M.

1988-09-01

A non-perturbative method using a Monte Carlo algorithm is used to integrate the Bethe-Salpeter equation in momentum space. Solutions for two scalars and two fermions with an arbitrary coupling constant are calculated for bound states in the ladder approximation. The results are compared with other numerical methods. (Author) (13 refs., 2 figs.)

Which test for CAD should be used in patients with left bundle branch block?

Science.gov (United States)

Xu, Bo; Cremer, Paul; Jaber, Wael; Moir, Stuart; Harb, Serge C; Rodriguez, L Leonardo

2018-03-01

Exercise stress electrocardiography is unreliable as a test for obstructive coronary artery disease (CAD) if the patient has left bundle branch block. The authors provide an algorithm for using alternative tests: exercise stress echocardiography, dobutamine echocardiography, computed tomographic (CT) angiography, and nuclear myocardial perfusion imaging. Copyright © 2018 Cleveland Clinic.

Empirical study of parallel LRU simulation algorithms

Science.gov (United States)

Carr, Eric; Nicol, David M.

1994-01-01

This paper reports on the performance of five parallel algorithms for simulating a fully associative cache operating under the LRU (Least-Recently-Used) replacement policy. Three of the algorithms are SIMD, and are implemented on the MasPar MP-2 architecture. Two other algorithms are parallelizations of an efficient serial algorithm on the Intel Paragon. One SIMD algorithm is quite simple, but its cost is linear in the cache size. The two other SIMD algorithm are more complex, but have costs that are independent on the cache size. Both the second and third SIMD algorithms compute all stack distances; the second SIMD algorithm is completely general, whereas the third SIMD algorithm presumes and takes advantage of bounds on the range of reference tags. Both MIMD algorithm implemented on the Paragon are general and compute all stack distances; they differ in one step that may affect their respective scalability. We assess the strengths and weaknesses of these algorithms as a function of problem size and characteristics, and compare their performance on traces derived from execution of three SPEC benchmark programs.

Robust branch-cut-and-price for the Capacitated Minimum Spanning Tree problem over a large extended formulation

DEFF Research Database (Denmark)

Uchoa, Eduardo; Fukasawa, Ricardo; Lysgaard, Jens

2008-01-01

-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. Moreover, a novel feature is introduced in such kind of algorithms: powerful new cuts expressed over a very large set of variables are added, without increasing the complexity of the pricing subproblem......This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to q-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence problem in order to make it solvable in pseudo...... or the size of the LPs that are actually solved. Computational results on benchmark instances from the OR-Library show very significant improvements over previous algorithms. Several open instances could be solved to optimality....

The cost-constrained traveling salesman problem

Energy Technology Data Exchange (ETDEWEB)

Sokkappa, P.R.

1990-10-01

The Cost-Constrained Traveling Salesman Problem (CCTSP) is a variant of the well-known Traveling Salesman Problem (TSP). In the TSP, the goal is to find a tour of a given set of cities such that the total cost of the tour is minimized. In the CCTSP, each city is given a value, and a fixed cost-constraint is specified. The objective is to find a subtour of the cities that achieves maximum value without exceeding the cost-constraint. Thus, unlike the TSP, the CCTSP requires both selection and sequencing. As a consequence, most results for the TSP cannot be extended to the CCTSP. We show that the CCTSP is NP-hard and that no K-approximation algorithm or fully polynomial approximation scheme exists, unless P = NP. We also show that several special cases are polynomially solvable. Algorithms for the CCTSP, which outperform previous methods, are developed in three areas: upper bounding methods, exact algorithms, and heuristics. We found that a bounding strategy based on the knapsack problem performs better, both in speed and in the quality of the bounds, than methods based on the assignment problem. Likewise, we found that a branch-and-bound approach using the knapsack bound was superior to a method based on a common branch-and-bound method for the TSP. In our study of heuristic algorithms, we found that, when selecting modes for inclusion in the subtour, it is important to consider the neighborhood'' of the nodes. A node with low value that brings the subtour near many other nodes may be more desirable than an isolated node of high value. We found two types of repetition to be desirable: repetitions based on randomization in the subtour buildings process, and repetitions encouraging the inclusion of different subsets of the nodes. By varying the number and type of repetitions, we can adjust the computation time required by our method to obtain algorithms that outperform previous methods.

Improved Lower Bounds on the Price of Stability of Undirected Network Design Games

Science.gov (United States)

Bilò, Vittorio; Caragiannis, Ioannis; Fanelli, Angelo; Monaco, Gianpiero

Bounding the price of stability of undirected network design games with fair cost allocation is a challenging open problem in the Algorithmic Game Theory research agenda. Even though the generalization of such games in directed networks is well understood in terms of the price of stability (it is exactly H n , the n-th harmonic number, for games with n players), far less is known for network design games in undirected networks. The upper bound carries over to this case as well while the best known lower bound is 42/23 ≈ 1.826. For more restricted but interesting variants of such games such as broadcast and multicast games, sublogarithmic upper bounds are known while the best known lower bound is 12/7 ≈ 1.714. In the current paper, we improve the lower bounds as follows. We break the psychological barrier of 2 by showing that the price of stability of undirected network design games is at least 348/155 ≈ 2.245. Our proof uses a recursive construction of a network design game with a simple gadget as the main building block. For broadcast and multicast games, we present new lower bounds of 20/11 ≈ 1.818 and 1.862, respectively.

Resource-constrained project scheduling: computing lower bounds by solving minimum cut problems

NARCIS (Netherlands)

Möhring, R.H.; Nesetril, J.; Schulz, A.S.; Stork, F.; Uetz, Marc Jochen

1999-01-01

We present a novel approach to compute Lagrangian lower bounds on the objective function value of a wide class of resource-constrained project scheduling problems. The basis is a polynomial-time algorithm to solve the following scheduling problem: Given a set of activities with start-time dependent

Bounded Perturbation Regularization for Linear Least Squares Estimation

KAUST Repository

Ballal, Tarig

2017-10-18

This paper addresses the problem of selecting the regularization parameter for linear least-squares estimation. We propose a new technique called bounded perturbation regularization (BPR). In the proposed BPR method, a perturbation with a bounded norm is allowed into the linear transformation matrix to improve the singular-value structure. Following this, the problem is formulated as a min-max optimization problem. Next, the min-max problem is converted to an equivalent minimization problem to estimate the unknown vector quantity. The solution of the minimization problem is shown to converge to that of the ℓ2 -regularized least squares problem, with the unknown regularizer related to the norm bound of the introduced perturbation through a nonlinear constraint. A procedure is proposed that combines the constraint equation with the mean squared error (MSE) criterion to develop an approximately optimal regularization parameter selection algorithm. Both direct and indirect applications of the proposed method are considered. Comparisons with different Tikhonov regularization parameter selection methods, as well as with other relevant methods, are carried out. Numerical results demonstrate that the proposed method provides significant improvement over state-of-the-art methods.

A polynomial time algorithm for checking regularity of totally normed process algebra

NARCIS (Netherlands)

Yang, F.; Huang, H.

2015-01-01

A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra (PA) processes is given. Its time complexity is O(n 3 +mn) O(n3+mn), where n is the number of transition rules and m is the maximal length of the rules. The algorithm works for

Institutional Analysis of Bounded Rationality of the Contemporary Russians

Directory of Open Access Journals (Sweden)

Ivan V. Rozmainsky

2017-12-01

Full Text Available The paper argues that behavior of present-day Russians is inconsistent with standard Neoclassical economics and can be better explained by the synthesis of various branches of Institutionalism and Post Keynesianism. Authors try to show that the present-day Russians are characterized by bounded rationality when they invest in health and financial assets, by fits and starts spend their incomes and cannot predict future levels of these incomes. Sometimes such bounded rationality manifests itself as investor myopia – a phenomenon that describes a situation when people exclude future variables from consideration starting from some threshold point of time. Investor myopia can lead to negative investment in health via smoking and heavy drinking, and also generate non-rational saving behavior. Furthermore, the contemporary Russians behave in the opportunistic manner. In particular, in the course of important examination writing the majority of people prefer to cheat off. Finally, the social pressure modifies the consumptive choice of the present-day Russians; in other words, this choice is not intrinsic. These statements are verified on the base of opinion poll findings by authors in 2016 and 2017. Sample included 521 persons, mainly young people. These data are analyzed by means of econometric – binomial and multinomial logit-models. The results of these studies show that the contemporary Russians are really characterized by bounded rather than perfect rationality. One of the conclusions is that fee-paying educated students are significantly less rational in their saving choice.

Amoeba-inspired Tug-of-War algorithms for exploration-exploitation dilemma in extended Bandit Problem.

Science.gov (United States)

Aono, Masashi; Kim, Song-Ju; Hara, Masahiko; Munakata, Toshinori

2014-03-01

The true slime mold Physarum polycephalum, a single-celled amoeboid organism, is capable of efficiently allocating a constant amount of intracellular resource to its pseudopod-like branches that best fit the environment where dynamic light stimuli are applied. Inspired by the resource allocation process, the authors formulated a concurrent search algorithm, called the Tug-of-War (TOW) model, for maximizing the profit in the multi-armed Bandit Problem (BP). A player (gambler) of the BP should decide as quickly and accurately as possible which slot machine to invest in out of the N machines and faces an "exploration-exploitation dilemma." The dilemma is a trade-off between the speed and accuracy of the decision making that are conflicted objectives. The TOW model maintains a constant intracellular resource volume while collecting environmental information by concurrently expanding and shrinking its branches. The conservation law entails a nonlocal correlation among the branches, i.e., volume increment in one branch is immediately compensated by volume decrement(s) in the other branch(es). Owing to this nonlocal correlation, the TOW model can efficiently manage the dilemma. In this study, we extend the TOW model to apply it to a stretched variant of BP, the Extended Bandit Problem (EBP), which is a problem of selecting the best M-tuple of the N machines. We demonstrate that the extended TOW model exhibits better performances for 2-tuple-3-machine and 2-tuple-4-machine instances of EBP compared with the extended versions of well-known algorithms for BP, the ϵ-Greedy and SoftMax algorithms, particularly in terms of its short-term decision-making capability that is essential for the survival of the amoeba in a hostile environment. Copyright © 2013 Elsevier Ireland Ltd. All rights reserved.

EDDA: An Efficient Distributed Data Replication Algorithm in VANETs.

Science.gov (United States)

Zhu, Junyu; Huang, Chuanhe; Fan, Xiying; Guo, Sipei; Fu, Bin

2018-02-10

Efficient data dissemination in vehicular ad hoc networks (VANETs) is a challenging issue due to the dynamic nature of the network. To improve the performance of data dissemination, we study distributed data replication algorithms in VANETs for exchanging information and computing in an arbitrarily-connected network of vehicle nodes. To achieve low dissemination delay and improve the network performance, we control the number of message copies that can be disseminated in the network and then propose an efficient distributed data replication algorithm (EDDA). The key idea is to let the data carrier distribute the data dissemination tasks to multiple nodes to speed up the dissemination process. We calculate the number of communication stages for the network to enter into a balanced status and show that the proposed distributed algorithm can converge to a consensus in a small number of communication stages. Most of the theoretical results described in this paper are to study the complexity of network convergence. The lower bound and upper bound are also provided in the analysis of the algorithm. Simulation results show that the proposed EDDA can efficiently disseminate messages to vehicles in a specific area with low dissemination delay and system overhead.

EDDA: An Efficient Distributed Data Replication Algorithm in VANETs

Science.gov (United States)

Zhu, Junyu; Huang, Chuanhe; Fan, Xiying; Guo, Sipei; Fu, Bin

2018-01-01

Efficient data dissemination in vehicular ad hoc networks (VANETs) is a challenging issue due to the dynamic nature of the network. To improve the performance of data dissemination, we study distributed data replication algorithms in VANETs for exchanging information and computing in an arbitrarily-connected network of vehicle nodes. To achieve low dissemination delay and improve the network performance, we control the number of message copies that can be disseminated in the network and then propose an efficient distributed data replication algorithm (EDDA). The key idea is to let the data carrier distribute the data dissemination tasks to multiple nodes to speed up the dissemination process. We calculate the number of communication stages for the network to enter into a balanced status and show that the proposed distributed algorithm can converge to a consensus in a small number of communication stages. Most of the theoretical results described in this paper are to study the complexity of network convergence. The lower bound and upper bound are also provided in the analysis of the algorithm. Simulation results show that the proposed EDDA can efficiently disseminate messages to vehicles in a specific area with low dissemination delay and system overhead. PMID:29439443

Guaranteed Bounds on Information-Theoretic Measures of Univariate Mixtures Using Piecewise Log-Sum-Exp Inequalities

KAUST Repository

Nielsen, Frank; Sun, Ke

2016-01-01

does not admit a closed-form formula, it is in practice either estimated using costly Monte Carlo stochastic integration, approximated or bounded using various techniques. We present a fast and generic method that builds algorithmically closed

Bound and rebound states

International Nuclear Information System (INIS)

Orzalesi, C.A.

1979-01-01

In relativistic quantum theory, bound states generate forces in the crossed channel; such forces can affect the binding and self-consistent solutions should be sought for the bound-state problem. The author investigates how self-consistency can be achieved by successive approximations, in a simple scalar model and with successive relativistic eikonal approximations (EAs). Within the generalized ladder approximation, some exact properties of the resulting ''first generation'' bound states are discussed. The binding energies in this approximation are rather small even for rather large values of the primary coupling constant. The coupling of the constituent particles to the first-generation reggeon is determined by a suitable EA and a new generalized ladder amplitude is constructed with rungs given either by the primary gluons or by the first-generation reggeons. The resulting new (second-generation) bound states are found in a reggeized EA. The size of the corrections to the binding energies due to the rebinding effects is surprisingly large. The procedure is then iterated, so as to find - again in an EA - the third-generation bound states. The procedure is found to be self-consistent already at this stage: the third-generation bound states coincide with those of second generation, and no further rebinding takes place in the higher iterations of the approximation method. Features - good and bad - of the model are discussed, as well as the possible relevance of rebinding mechanisms in hadron dynamics. (author)

Fundamentals of natural computing basic concepts, algorithms, and applications

CERN Document Server

de Castro, Leandro Nunes

2006-01-01

Introduction A Small Sample of Ideas The Philosophy of Natural Computing The Three Branches: A Brief Overview When to Use Natural Computing Approaches Conceptualization General Concepts PART I - COMPUTING INSPIRED BY NATURE Evolutionary Computing Problem Solving as a Search Task Hill Climbing and Simulated Annealing Evolutionary Biology Evolutionary Computing The Other Main Evolutionary Algorithms From Evolutionary Biology to Computing Scope of Evolutionary Computing Neurocomputing The Nervous System Artif

Circuit lower bounds in bounded arithmetics

Czech Academy of Sciences Publication Activity Database

Pich, Ján

2015-01-01

Roč. 166, č. 1 (2015), s. 29-45 ISSN 0168-0072 R&D Projects: GA AV ČR IAA100190902 Keywords : bounded arithmetic * circuit lower bounds Subject RIV: BA - General Mathematics Impact factor: 0.582, year: 2015 http://www.sciencedirect.com/science/article/pii/S0168007214000888

The MUSIC algorithm for sparse objects: a compressed sensing analysis

International Nuclear Information System (INIS)

Fannjiang, Albert C

2011-01-01

The multiple signal classification (MUSIC) algorithm, and its extension for imaging sparse extended objects, with noisy data is analyzed by compressed sensing (CS) techniques. A thresholding rule is developed to augment the standard MUSIC algorithm. The notion of restricted isometry property (RIP) and an upper bound on the restricted isometry constant (RIC) are employed to establish sufficient conditions for the exact localization by MUSIC with or without noise. In the noiseless case, the sufficient condition gives an upper bound on the numbers of random sampling and incident directions necessary for exact localization. In the noisy case, the sufficient condition assumes additionally an upper bound for the noise-to-object ratio in terms of the RIC and the dynamic range of objects. This bound points to the super-resolution capability of the MUSIC algorithm. Rigorous comparison of performance between MUSIC and the CS minimization principle, basis pursuit denoising (BPDN), is given. In general, the MUSIC algorithm guarantees to recover, with high probability, s scatterers with n=O(s 2 ) random sampling and incident directions and sufficiently high frequency. For the favorable imaging geometry where the scatterers are distributed on a transverse plane MUSIC guarantees to recover, with high probability, s scatterers with a median frequency and n=O(s) random sampling/incident directions. Moreover, for the problems of spectral estimation and source localizations both BPDN and MUSIC guarantee, with high probability, to identify exactly the frequencies of random signals with the number n=O(s) of sampling times. However, in the absence of abundant realizations of signals, BPDN is the preferred method for spectral estimation. Indeed, BPDN can identify the frequencies approximately with just one realization of signals with the recovery error at worst linearly proportional to the noise level. Numerical results confirm that BPDN outperforms MUSIC in the well-resolved case while

Branched polynomial covering maps

DEFF Research Database (Denmark)

Hansen, Vagn Lundsgaard

1999-01-01

A Weierstrass polynomial with multiple roots in certain points leads to a branched covering map. With this as the guiding example, we formally define and study the notion of a branched polynomial covering map. We shall prove that many finite covering maps are polynomial outside a discrete branch...... set. Particular studies are made of branched polynomial covering maps arising from Riemann surfaces and from knots in the 3-sphere....

Critical evaluation of branch polarity and apical dominance as dictators of colony astogeny in a branching coral.

Directory of Open Access Journals (Sweden)

Lee Shaish

Full Text Available The high morphological resemblance between branching corals and trees, can lead to comparative studies on pattern formation traits, best exemplified in plants and in some cnidarians. Here, 81 branches of similar size of the hermatypic coral Stylophora pistillata were lopped of three different genets, their skeletons marked with alizarin red-S, and divided haphazardly into three morphometric treatment groups: (I upright position; (II horizontal position, intact tip; and (III horizontal position, cut tip. After 1 y of in-situ growth, the 45 surviving ramets were brought to the laboratory, their tissues removed and their architectures analyzed by 22 morphological parameters (MPs. We found that within 1 y, isolated branches developed into small coral colonies by growing new branches from all branch termini, in all directions. No architectural dissimilarity was assigned among the three studied genets of treatment I colonies. However, a major architectural disparity between treatment I colonies and colonies of treatments II and III was documented as the development of mirror structures from both sides of treatments II and III settings as compared to tip-borne architectures in treatment I colonies. We did not observe apical dominance since fragments grew equally from all branch sides without documented dominant polarity along branch axis. In treatment II colonies, no MP for new branches originating either from tips or from branch bases differed significantly. In treatment III colonies, growth from the cut tip areas was significantly lower compared to the base, again, suggesting lack of apical dominance in this species. Changes in branch polarity revealed genet associated plasticity, which in one of the studied genets, led to enhanced growth. Different genets exhibited canalization flexibility of growth patterns towards either lateral growth, or branch axis extension (skeletal weight and not porosity was measured. This study revealed that colony

The Cramér-Rao Bounds and Sensor Selection for Nonlinear Systems with Uncertain Observations.

Science.gov (United States)

Wang, Zhiguo; Shen, Xiaojing; Wang, Ping; Zhu, Yunmin

2018-04-05

This paper considers the problems of the posterior Cramér-Rao bound and sensor selection for multi-sensor nonlinear systems with uncertain observations. In order to effectively overcome the difficulties caused by uncertainty, we investigate two methods to derive the posterior Cramér-Rao bound. The first method is based on the recursive formula of the Cramér-Rao bound and the Gaussian mixture model. Nevertheless, it needs to compute a complex integral based on the joint probability density function of the sensor measurements and the target state. The computation burden of this method is relatively high, especially in large sensor networks. Inspired by the idea of the expectation maximization algorithm, the second method is to introduce some 0-1 latent variables to deal with the Gaussian mixture model. Since the regular condition of the posterior Cramér-Rao bound is unsatisfied for the discrete uncertain system, we use some continuous variables to approximate the discrete latent variables. Then, a new Cramér-Rao bound can be achieved by a limiting process of the Cramér-Rao bound of the continuous system. It avoids the complex integral, which can reduce the computation burden. Based on the new posterior Cramér-Rao bound, the optimal solution of the sensor selection problem can be derived analytically. Thus, it can be used to deal with the sensor selection of a large-scale sensor networks. Two typical numerical examples verify the effectiveness of the proposed methods.

Constraint Optimization for Highly Constrained Logistic Problems

DEFF Research Database (Denmark)

Mochnacs, Maria Kinga; Tanaka, Meang Akira; Nyborg, Anders

This report investigates whether propagators combined with branch and bound algorithm are suitable for solving the storage area stowage problem within reasonable time. The approach has not been attempted before and experiments show that the implementation was not capable of solving the storage ar...

An analytic parton shower. Algorithms, implementation and validation

Energy Technology Data Exchange (ETDEWEB)

Schmidt, Sebastian

2012-06-15

The realistic simulation of particle collisions is an indispensable tool to interpret the data measured at high-energy colliders, for example the now running Large Hadron Collider at CERN. These collisions at these colliders are usually simulated in the form of exclusive events. This thesis focuses on the perturbative QCD part involved in the simulation of these events, particularly parton showers and the consistent combination of parton showers and matrix elements. We present an existing parton shower algorithm for emissions off final state partons along with some major improvements. Moreover, we present a new parton shower algorithm for emissions off incoming partons. The aim of these particular algorithms, called analytic parton shower algorithms, is to be able to calculate the probabilities for branchings and for whole events after the event has been generated. This allows a reweighting procedure to be applied after the events have been simulated. We show a detailed description of the algorithms, their implementation and the interfaces to the event generator WHIZARD. Moreover we discuss the implementation of a MLM-type matching procedure and an interface to the shower and hadronization routines from PYTHIA. Finally, we compare several predictions by our implementation to experimental measurements at LEP, Tevatron and LHC, as well as to predictions obtained using PYTHIA. (orig.)

An analytic parton shower. Algorithms, implementation and validation

International Nuclear Information System (INIS)

Schmidt, Sebastian

2012-06-01

The realistic simulation of particle collisions is an indispensable tool to interpret the data measured at high-energy colliders, for example the now running Large Hadron Collider at CERN. These collisions at these colliders are usually simulated in the form of exclusive events. This thesis focuses on the perturbative QCD part involved in the simulation of these events, particularly parton showers and the consistent combination of parton showers and matrix elements. We present an existing parton shower algorithm for emissions off final state partons along with some major improvements. Moreover, we present a new parton shower algorithm for emissions off incoming partons. The aim of these particular algorithms, called analytic parton shower algorithms, is to be able to calculate the probabilities for branchings and for whole events after the event has been generated. This allows a reweighting procedure to be applied after the events have been simulated. We show a detailed description of the algorithms, their implementation and the interfaces to the event generator WHIZARD. Moreover we discuss the implementation of a MLM-type matching procedure and an interface to the shower and hadronization routines from PYTHIA. Finally, we compare several predictions by our implementation to experimental measurements at LEP, Tevatron and LHC, as well as to predictions obtained using PYTHIA. (orig.)

Search for weakly decaying Λn‾ and ΛΛ exotic bound states in central Pb–Pb collisions at sNN=2.76 TeV

Directory of Open Access Journals (Sweden)

J. Adam

2016-01-01

Full Text Available We present results of a search for two hypothetical strange dibaryon states, i.e. the H-dibaryon and the possible Λn‾ bound state. The search is performed with the ALICE detector in central (0–10% Pb–Pb collisions at sNN=2.76 TeV, by invariant mass analysis in the decay modes Λn‾→d‾π+ and H-dibaryon →Λpπ−. No evidence for these bound states is observed. Upper limits are determined at 99% confidence level for a wide range of lifetimes and for the full range of branching ratios. The results are compared to thermal, coalescence and hybrid UrQMD model expectations, which describe correctly the production of other loosely bound states, like the deuteron and the hypertriton.

Hybrid Robust Multi-Objective Evolutionary Optimization Algorithm

Science.gov (United States)

2009-03-10

xfar by xint. Else, generate a new individual, using the Sobol pseudo- random sequence generator within the upper and lower bounds of the variables...12. Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons. 2002. 13. Sobol , I. M., "Uniformly Distributed Sequences

Multi-modal distribution crossover method based on two crossing segments bounded by selected parents applied to multi-objective design optimization

Energy Technology Data Exchange (ETDEWEB)

Ariyarit, Atthaphon; Kanazaki, Masahiro [Tokyo Metropolitan University, Tokyo (Japan)

2015-04-15

This paper discusses airfoil design optimization using a genetic algorithm (GA) with multi-modal distribution crossover (MMDX). The proposed crossover method creates four segments from four parents, of which two segments are bounded by selected parents and two segments are bounded by one parent and another segment. After these segments are defined, four offsprings are generated. This study applied the proposed optimization to a real-world, multi-objective airfoil design problem using class-shape function transformation parameterization, which is an airfoil representation that uses polynomial function, to investigate the effectiveness of this algorithm. The results are compared with the results of the blend crossover (BLX) and unimodal normal distribution crossover (UNDX) algorithms. The objective of these airfoil design problems is to successfully find the optimal design. The outcome of using this algorithm is superior to that of the BLX and UNDX crossover methods because the proposed method can maintain higher diversity than the BLX and UNDX methods. This advantage is desirable for real-world problems.

Multi-modal distribution crossover method based on two crossing segments bounded by selected parents applied to multi-objective design optimization

International Nuclear Information System (INIS)

Ariyarit, Atthaphon; Kanazaki, Masahiro

2015-01-01

This paper discusses airfoil design optimization using a genetic algorithm (GA) with multi-modal distribution crossover (MMDX). The proposed crossover method creates four segments from four parents, of which two segments are bounded by selected parents and two segments are bounded by one parent and another segment. After these segments are defined, four offsprings are generated. This study applied the proposed optimization to a real-world, multi-objective airfoil design problem using class-shape function transformation parameterization, which is an airfoil representation that uses polynomial function, to investigate the effectiveness of this algorithm. The results are compared with the results of the blend crossover (BLX) and unimodal normal distribution crossover (UNDX) algorithms. The objective of these airfoil design problems is to successfully find the optimal design. The outcome of using this algorithm is superior to that of the BLX and UNDX crossover methods because the proposed method can maintain higher diversity than the BLX and UNDX methods. This advantage is desirable for real-world problems.

Optimization of a permanent magnet synchronous machine with respect to variable loads; Optimierung einer permanenterregten Synchronmaschine unter Beruecksichtigung von Lastspielen

Energy Technology Data Exchange (ETDEWEB)

Kreim, Alexander; Schaefer, Uwe [TU Berlin (Germany). Sek. EM4 Elektrische Antriebstechnik

2010-10-15

This article introduces a nonlinear optimization algorithm for mixed integer problems. The proposed algorithm is a trust region algorithm for an exact penalty function. The quadratic subproblem is used for the integration of discrete variables. This is done by a branch-and-bound approach. The application of the algorithm is shown by minimizing the losses of a permanent magnet synchronous machine. The machine is designed for use in hybrid and electric vehicles. It is shown how load cycles can be included into the optimization process. (orig.)

A duty-period-based formulation of the airline crew scheduling problem

Energy Technology Data Exchange (ETDEWEB)

Hoffman, K.

1994-12-31

We present a new formulation of the airline crew scheduling problem that explicitly considers the duty periods. We suggest an algorithm for solving the formulation by a column generation approach with branch-and-bound. Computational results are reported for a number of test problems.

Branch Width and Height Influence the Incorporation of Branches into Foraging Trails and Travel Speed in Leafcutter Ants Atta cephalotes (L.) (Hymenoptera: Formicidae).

Science.gov (United States)

Freeman, B M; Chaves-Campos, J

2016-06-01

Fallen branches are often incorporated into Atta cephalotes (L.) foraging trails to optimize leaf tissue transport rates and economize trail maintenance. Recent studies in lowlands show laden A. cephalotes travel faster across fallen branches than on ground, but more slowly ascending or descending a branch. The latter is likely because (1) it is difficult to travel up or downhill and (2) bottlenecks occur when branches are narrower than preceding trail. Hence, both branch height and width should determine whether branches decrease net travel times, but no study has evaluated it yet. Laden A. cephalotes were timed in relation to branch width and height across segments preceding, accessing, across, and departing a fallen branch in the highlands of Costa Rica. Ants traveled faster on branches than on cleared segments of trunk-trail, but accelerated when ascending or descending the branch-likely because of the absence of bottlenecks during the day in the highlands. Branch size did not affect ant speed in observed branches; the majority of which (22/24) varied from 11 to 120 mm in both height and width (average 66 mm in both cases). To determine whether ants exclude branches outside this range, ants were offered the choice between branches within this range and branches that were taller/wider than 120 mm. Ants strongly preferred the former. Our results indicate that A. cephalotes can adjust their speed to compensate for the difficulty of traveling on branch slopes. More generally, branch size should be considered when studying ant foraging efficiency.

Optimization of Algorithms Using Extensions of Dynamic Programming

KAUST Repository

AbouEisha, Hassan M.

2017-04-09

We study and answer questions related to the complexity of various important problems such as: multi-frontal solvers of hp-adaptive finite element method, sorting and majority. We advocate the use of dynamic programming as a viable tool to study optimal algorithms for these problems. The main approach used to attack these problems is modeling classes of algorithms that may solve this problem using a discrete model of computation then defining cost functions on this discrete structure that reflect different complexity measures of the represented algorithms. As a last step, dynamic programming algorithms are designed and used to optimize those models (algorithms) and to obtain exact results on the complexity of the studied problems. The first part of the thesis presents a novel model of computation (element partition tree) that represents a class of algorithms for multi-frontal solvers along with cost functions reflecting various complexity measures such as: time and space. It then introduces dynamic programming algorithms for multi-stage and bi-criteria optimization of element partition trees. In addition, it presents results based on optimal element partition trees for famous benchmark meshes such as: meshes with point and edge singularities. New improved heuristics for those benchmark meshes were ob- tained based on insights of the optimal results found by our algorithms. The second part of the thesis starts by introducing a general problem where different problems can be reduced to and show how to use a decision table to model such problem. We describe how decision trees and decision tests for this table correspond to adaptive and non-adaptive algorithms for the original problem. We present exact bounds on the average time complexity of adaptive algorithms for the eight elements sorting problem. Then bounds on adaptive and non-adaptive algorithms for a variant of the majority problem are introduced. Adaptive algorithms are modeled as decision trees whose depth

Parameter identification for structural dynamics based on interval analysis algorithm

Science.gov (United States)

Yang, Chen; Lu, Zixing; Yang, Zhenyu; Liang, Ke

2018-04-01

A parameter identification method using interval analysis algorithm for structural dynamics is presented in this paper. The proposed uncertain identification method is investigated by using central difference method and ARMA system. With the help of the fixed memory least square method and matrix inverse lemma, a set-membership identification technology is applied to obtain the best estimation of the identified parameters in a tight and accurate region. To overcome the lack of insufficient statistical description of the uncertain parameters, this paper treats uncertainties as non-probabilistic intervals. As long as we know the bounds of uncertainties, this algorithm can obtain not only the center estimations of parameters, but also the bounds of errors. To improve the efficiency of the proposed method, a time-saving algorithm is presented by recursive formula. At last, to verify the accuracy of the proposed method, two numerical examples are applied and evaluated by three identification criteria respectively.

Entanglement branching operator

Science.gov (United States)

Harada, Kenji

2018-01-01

We introduce an entanglement branching operator to split a composite entanglement flow in a tensor network which is a promising theoretical tool for many-body systems. We can optimize an entanglement branching operator by solving a minimization problem based on squeezing operators. The entanglement branching is a new useful operation to manipulate a tensor network. For example, finding a particular entanglement structure by an entanglement branching operator, we can improve a higher-order tensor renormalization group method to catch a proper renormalization flow in a tensor network space. This new method yields a new type of tensor network states. The second example is a many-body decomposition of a tensor by using an entanglement branching operator. We can use it for a perfect disentangling among tensors. Applying a many-body decomposition recursively, we conceptually derive projected entangled pair states from quantum states that satisfy the area law of entanglement entropy.

Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors

DEFF Research Database (Denmark)

Arge, Lars Allan; Goodrich, Michael T.; Nelson, Michael

2008-01-01

about the way cores are interconnected, for we assume that all inter-processor communication occurs through the memory hierarchy. We study several fundamental problems, including prefix sums, selection, and sorting, which often form the building blocks of other parallel algorithms. Indeed, we present...... two sorting algorithms, a distribution sort and a mergesort. Our algorithms are asymptotically optimal in terms of parallel cache accesses and space complexity under reasonable assumptions about the relationships between the number of processors, the size of memory, and the size of cache blocks....... In addition, we study sorting lower bounds in a computational model, which we call the parallel external-memory (PEM) model, that formalizes the essential properties of our algorithms for private-cache CMPs....

Bounds on Average Time Complexity of Decision Trees

KAUST Repository

Chikalov, Igor

2011-01-01

In this chapter, bounds on the average depth and the average weighted depth of decision trees are considered. Similar problems are studied in search theory [1], coding theory [77], design and analysis of algorithms (e.g., sorting) [38]. For any diagnostic problem, the minimum average depth of decision tree is bounded from below by the entropy of probability distribution (with a multiplier 1/log2 k for a problem over a k-valued information system). Among diagnostic problems, the problems with a complete set of attributes have the lowest minimum average depth of decision trees (e.g, the problem of building optimal prefix code [1] and a blood test study in assumption that exactly one patient is ill [23]). For such problems, the minimum average depth of decision tree exceeds the lower bound by at most one. The minimum average depth reaches the maximum on the problems in which each attribute is "indispensable" [44] (e.g., a diagnostic problem with n attributes and kn pairwise different rows in the decision table and the problem of implementing the modulo 2 summation function). These problems have the minimum average depth of decision tree equal to the number of attributes in the problem description. © Springer-Verlag Berlin Heidelberg 2011.

Speeding up Online POMDP planning - unification of observation branches by belief-state compression via expected feature values

CSIR Research Space (South Africa)

Rens, G

2015-01-01

Full Text Available A novel algorithm to speed up online planning in partially observable Markov decision processes (POMDPs) is introduced. I propose a method for compressing nodes in belief-decision-trees while planning occurs. Whereas belief-decision-trees branch...

Improved quantum backtracking algorithms using effective resistance estimates

Science.gov (United States)

Jarret, Michael; Wan, Kianna

2018-02-01

We investigate quantum backtracking algorithms of the type introduced by Montanaro (Montanaro, arXiv:1509.02374). These algorithms explore trees of unknown structure and in certain settings exponentially outperform their classical counterparts. Some of the previous work focused on obtaining a quantum advantage for trees in which a unique marked vertex is promised to exist. We remove this restriction by recharacterizing the problem in terms of the effective resistance of the search space. In this paper, we present a generalization of one of Montanaro's algorithms to trees containing k marked vertices, where k is not necessarily known a priori. Our approach involves using amplitude estimation to determine a near-optimal weighting of a diffusion operator, which can then be applied to prepare a superposition state with support only on marked vertices and ancestors thereof. By repeatedly sampling this state and updating the input vertex, a marked vertex is reached in a logarithmic number of steps. The algorithm thereby achieves the conjectured bound of O ˜(√{T Rmax }) for finding a single marked vertex and O ˜(k √{T Rmax }) for finding all k marked vertices, where T is an upper bound on the tree size and Rmax is the maximum effective resistance encountered by the algorithm. This constitutes a speedup over Montanaro's original procedure in both the case of finding one and the case of finding multiple marked vertices in an arbitrary tree.

Anisotropic inflation reexamined: upper bound on broken rotational invariance during inflation

International Nuclear Information System (INIS)

Naruko, Atsushi; Yamaguchi, Masahide; Komatsu, Eiichiro

2015-01-01

The presence of a light vector field coupled to a scalar field during inflation makes a distinct prediction: the observed correlation functions of the cosmic microwave background (CMB) become statistically anisotropic. We study the implications of the current bound on statistical anisotropy derived from the Planck 2013 CMB temperature data for such a model. The previous calculations based on the attractor solution indicate that the magnitude of anisotropy in the power spectrum is proportional to N 2 , where N is the number of e-folds of inflation counted from the end of inflation. In this paper, we show that the attractor solution is not necessarily compatible with the current bound, and derive new predictions using another branch of anisotropic inflation. In addition, we improve upon the calculation of the mode function of perturbations by including the leading-order slow-roll corrections. We find that the anisotropy is roughly proportional to [2(ε H +4η H )/3−4(c−1)] −2 , where ε H and η H are the usual slow-roll parameters and c is the parameter in the model, regardless of the form of potential of an inflaton field. The bound from Planck implies that breaking of rotational invariance during inflation (characterized by the background homogeneous shear divided by the Hubble rate) is limited to be less than O(10 −9 ). This bound is many orders of magnitude smaller than the amplitude of breaking of time translation invariance, which is observed to be O(10 −2 )

Some uses of the symmetric Lanczos algorithm - and why it works!

Energy Technology Data Exchange (ETDEWEB)

Druskin, V.L. [Schlumberger-Doll Research, Ridgefield, CT (United States); Greenbaum, A. [Courant Institute of Mathematical Sciences, New York, NY (United States); Knizhnerman, L.A. [Central Geophysical Expedition, Moscow (Russian Federation)

1996-12-31

The Lanczos algorithm uses a three-term recurrence to construct an orthonormal basis for the Krylov space corresponding to a symmetric matrix A and a starting vector q{sub 1}. The vectors and recurrence coefficients produced by this algorithm can be used for a number of purposes, including solving linear systems Au = {var_phi} and computing the matrix exponential e{sup -tA}{var_phi}. Although the vectors produced in finite precision arithmetic are not orthogonal, we show why they can still be used effectively for these purposes. The reason is that the 2-norm of the residual is essentially determined by the tridiagonal matrix and the next recurrence coefficient produced by the finite precision Lanczos computation. It follows that if the same tridiagonal matrix and recurrence coefficient are produced by the exact Lanczos algorithm applied to some other problem, then exact arithmetic bounds on the residual for that problem will hold for the finite precision computation. In order to establish exact arithmetic bounds for the different problem, it is necessary to have some information about the eigenvalues of the new coefficient matrix. Here we make use of information already established in the literature, and we also prove a new result for indefinite matrices.

Robustness bounds and practical limitations of quantum key distribution

International Nuclear Information System (INIS)

Khalique, Aeysha

2008-01-01

Quantum information theory is a modern branch of theoretical physics. One of its main goals is to interpret concepts of quantum physics. This leads to a deeper understanding of quantum theory. The most common examples of practical applications of basic quantum theory are quantum computation and quantum cryptography. Quantum cryptography provides secure communication between legitimate users even in the presence of an adversary by making possible the distribution of a secret key. It then allows error correction and privacy amplification, which is elimination of adversary information, through classical communication. In this thesis two important aspects of quantum key distribution are covered, namely robustness bounds with respect to provable entanglement for ideal protocols and practical quantum key distribution using two-way classical communication. In part one of the thesis, ideal quantum key distribution protocols and their robustness in terms of provable entanglement are discussed. The robustness bounds are proved for most general coherent attacks. These bounds for provable entanglement are already known to be 25% for the four-state protocol and 33% for the six-state protocol. We anticipate to provide a region in which the legitimate users share entanglement. This region is large for the four-state protocol and is reduced to a smaller region for the six-state protocol because of additional constraint on it. We also investigate the information cost which the adversary has to pay in order to reach these bounds. In part two we adopt a more practical approach. We investigate the limitation on distance of secure communication because of practical restrictions. In particular we investigate the restrictions due to the lack of single photon sources, the lossy channel and faulty detectors. These practical limitations have already been observed using one-way classical communication between legitimate users. It has been observed that it is actually the dark count rate that

A branch and cut approach to the multiproduct pipeline scheduling problem

Energy Technology Data Exchange (ETDEWEB)

Souza Filho, Erito Marques de; Bahiense, Laura; Ferreira Filho, Virgilio Jose Martins [Universidade Federal do Rio de Janeiro (UFRJ), RJ (Brazil)

2009-07-01

Pipelines are known as the most reliable and economical mode of transportation for petroleum and its derivatives, especially when large amounts of products have to be pumped for large distances. We address the short-term schedule of a pipeline system comprising the distribution of several petroleum derivatives from a single oil refinery to several depots, connected to local consumer markets, through a single multi-product pipeline. The major difficulties faced in these operations are related to the satisfaction of product demands by the various consumer markets, and operational constraints such as the maximum sizes of contiguous pumping packs, and the immiscible products. Several researchers have developed models and techniques for this short-term pipeline scheduling problem. Two different methodologies have been proposed in the literature: heuristic search techniques and exact methods. In this paper, we use a branch-and cut algorithm, performed in Xpress-MP{sup T}M, and compare the solutions obtained with that ones obtained before using the Variable Neighborhood Search metaheuristic. The computational results showed a significant improvement of performance in relation to previous algorithm. (author)

Minimum Probability of Error-Based Equalization Algorithms for Fading Channels

Directory of Open Access Journals (Sweden)

Janos Levendovszky

2007-06-01

Full Text Available Novel channel equalizer algorithms are introduced for wireless communication systems to combat channel distortions resulting from multipath propagation. The novel algorithms are based on newly derived bounds on the probability of error (PE and guarantee better performance than the traditional zero forcing (ZF or minimum mean square error (MMSE algorithms. The new equalization methods require channel state information which is obtained by a fast adaptive channel identification algorithm. As a result, the combined convergence time needed for channel identification and PE minimization still remains smaller than the convergence time of traditional adaptive algorithms, yielding real-time equalization. The performance of the new algorithms is tested by extensive simulations on standard mobile channels.

Algorithms for Calculating Alternating Infinite Series

International Nuclear Information System (INIS)

Garcia, Hector Luna; Garcia, Luz Maria

2015-01-01

This paper are presented novel algorithms for exact limits of a broad class of infinite alternating series. Many of these series are found in physics and other branches of science and their exact values found for us are in complete agreement with the values obtained by other authors. Finally, these simple methods are very powerful in calculating the limits of many series as shown by the examples

Efficient Out of Core Sorting Algorithms for the Parallel Disks Model.

Science.gov (United States)

Kundeti, Vamsi; Rajasekaran, Sanguthevar

2011-11-01

In this paper we present efficient algorithms for sorting on the Parallel Disks Model (PDM). Numerous asymptotically optimal algorithms have been proposed in the literature. However many of these merge based algorithms have large underlying constants in the time bounds, because they suffer from the lack of read parallelism on PDM. The irregular consumption of the runs during the merge affects the read parallelism and contributes to the increased sorting time. In this paper we first introduce a novel idea called the dirty sequence accumulation that improves the read parallelism. Secondly, we show analytically that this idea can reduce the number of parallel I/O's required to sort the input close to the lower bound of [Formula: see text]. We experimentally verify our dirty sequence idea with the standard R-Way merge and show that our idea can reduce the number of parallel I/Os to sort on PDM significantly.

Upper Bounds Prediction of the Execution Time of Programs Running on ARM Cortex-A Systems

OpenAIRE

Fedotova , Irina; Krause , Bernd; Siemens , Eduard

2017-01-01

Part 6: Embedded and Real Time Systems; International audience; This paper describes the application of statistical analysis of the timing behavior for a generic real-time task model. Using specific processor of ARM Cortex-A series and an empirical approach of time values retrieval, the algorithm to predict the upper bounds for the task of the time acquisition operation has been formulated. For the experimental verification of the algorithm, we have used the robust Measurement-Based Probabili...

A simple greedy algorithm for dynamic graph orientation

DEFF Research Database (Denmark)

Berglin, Edvin; Brodal, Gerth Stølting

2017-01-01

Graph orientations with low out-degree are one of several ways to efficiently store sparse graphs. If the graphs allow for insertion and deletion of edges, one may have to flip the orientation of some edges to prevent blowing up the maximum out-degree. We use arboricity as our sparsity measure....... With an immensely simple greedy algorithm, we get parametrized trade-off bounds between out-degree and worst case number of flips, which previously only existed for amortized number of flips. We match the previous best worst-case algorithm (in O(log n) flips) for general arboricity and beat it for either constant...... or super-logarithmic arboricity. We also match a previous best amortized result for at least logarithmic arboricity, and give the first results with worst-case O(1) and O(sqrt(log n)) flips nearly matching degree bounds to their respective amortized solutions....

Unified compression and encryption algorithm for fast and secure network communications

International Nuclear Information System (INIS)

Rizvi, S.M.J.; Hussain, M.; Qaiser, N.

2005-01-01

Compression and encryption of data are two vital requirements for the fast and secure transmission of data in the network based communications. In this paper an algorithm is presented based on adaptive Huffman encoding for unified compression and encryption of Unicode encoded textual data. The Huffman encoding weakness that same tree is needed for decoding is utilized in the algorithm presented as an extra layer of security, which is updated whenever the frequency change is above the specified threshold level. The results show that we get compression comparable to popular zip format and in addition to that data has got an additional layer of encryption that makes it more secure. Thus unified algorithm presented here can be used for network communications between different branches of banks, e- Government programs and national database and registration centers where data transmission requires both compression and encryption. (author)

ALGORITHME POUR LE CALCUL DES COURBURES GENERALISEES

Directory of Open Access Journals (Sweden)

K MEZAGHCHA

2004-06-01

Full Text Available On sait qu’une courbe algébrique standard  d'équation f(x, y =0 admet un nombre fini de branches (nombre inférieur à l'ordre de f , dont les paramètrages peuvent être obtenus en particulier à partir de la décomposition de Goze itérée. On aimerait calculer  leur courbure généralisée sans les déterminer explicitement, la notion de courbure généralisée ayant fait l’objet d’un travail, publié dans les comptes rendus de l’Université de Cagliari (Italie [12]. Dans cet article, on se propose d'établir à cet effet un algorithme qui donnera à partir seulement des coefficients de f, la liste exhaustive des courbures généralisées de toutes les branches réelles. L’article se termine par la donnée d’un exemple pour montrer l’efficacité de l’algorithme proposé.

EDDA: An Efficient Distributed Data Replication Algorithm in VANETs

Directory of Open Access Journals (Sweden)

Junyu Zhu

2018-02-01

Full Text Available Efficient data dissemination in vehicular ad hoc networks (VANETs is a challenging issue due to the dynamic nature of the network. To improve the performance of data dissemination, we study distributed data replication algorithms in VANETs for exchanging information and computing in an arbitrarily-connected network of vehicle nodes. To achieve low dissemination delay and improve the network performance, we control the number of message copies that can be disseminated in the network and then propose an efficient distributed data replication algorithm (EDDA. The key idea is to let the data carrier distribute the data dissemination tasks to multiple nodes to speed up the dissemination process. We calculate the number of communication stages for the network to enter into a balanced status and show that the proposed distributed algorithm can converge to a consensus in a small number of communication stages. Most of the theoretical results described in this paper are to study the complexity of network convergence. The lower bound and upper bound are also provided in the analysis of the algorithm. Simulation results show that the proposed EDDA can efficiently disseminate messages to vehicles in a specific area with low dissemination delay and system overhead.

Phase-unwrapping algorithm by a rounding-least-squares approach

Science.gov (United States)

Juarez-Salazar, Rigoberto; Robledo-Sanchez, Carlos; Guerrero-Sanchez, Fermin

2014-02-01

A simple and efficient phase-unwrapping algorithm based on a rounding procedure and a global least-squares minimization is proposed. Instead of processing the gradient of the wrapped phase, this algorithm operates over the gradient of the phase jumps by a robust and noniterative scheme. Thus, the residue-spreading and over-smoothing effects are reduced. The algorithm's performance is compared with four well-known phase-unwrapping methods: minimum cost network flow (MCNF), fast Fourier transform (FFT), quality-guided, and branch-cut. A computer simulation and experimental results show that the proposed algorithm reaches a high-accuracy level than the MCNF method by a low-computing time similar to the FFT phase-unwrapping method. Moreover, since the proposed algorithm is simple, fast, and user-free, it could be used in metrological interferometric and fringe-projection automatic real-time applications.

A flooding algorithm for multirobot exploration.

Science.gov (United States)

Cabrera-Mora, Flavio; Xiao, Jizhong

2012-06-01

In this paper, we present a multirobot exploration algorithm that aims at reducing the exploration time and to minimize the overall traverse distance of the robots by coordinating the movement of the robots performing the exploration. Modeling the environment as a tree, we consider a coordination model that restricts the number of robots allowed to traverse an edge and to enter a vertex during each step. This coordination is achieved in a decentralized manner by the robots using a set of active landmarks that are dropped by them at explored vertices. We mathematically analyze the algorithm on trees, obtaining its main properties and specifying its bounds on the exploration time. We also define three metrics of performance for multirobot algorithms. We simulate and compare the performance of this new algorithm with those of our multirobot depth first search (MR-DFS) approach presented in our recent paper and classic single-robot DFS.

A Developed ESPRIT Algorithm for DOA Estimation

Science.gov (United States)

Fayad, Youssef; Wang, Caiyun; Cao, Qunsheng; Hafez, Alaa El-Din Sayed

2015-05-01

A novel algorithm for estimating direction of arrival (DOAE) for target, which aspires to contribute to increase the estimation process accuracy and decrease the calculation costs, has been carried out. It has introduced time and space multiresolution in Estimation of Signal Parameter via Rotation Invariance Techniques (ESPRIT) method (TS-ESPRIT) to realize subspace approach that decreases errors caused by the model's nonlinearity effect. The efficacy of the proposed algorithm is verified by using Monte Carlo simulation, the DOAE accuracy has evaluated by closed-form Cramér-Rao bound (CRB) which reveals that the proposed algorithm's estimated results are better than those of the normal ESPRIT methods leading to the estimator performance enhancement.

3rd Workshop on Branching Processes and their Applications

CERN Document Server

González, Miguel; Gutiérrez, Cristina; Martínez, Rodrigo; Minuesa, Carmen; Molina, Manuel; Mota, Manuel; Ramos, Alfonso; WBPA15

2016-01-01

This volume gathers papers originally presented at the 3rd Workshop on Branching Processes and their Applications (WBPA15), which was held from 7 to 10 April 2015 in Badajoz, Spain (http://branching.unex.es/wbpa15/index.htm). The papers address a broad range of theoretical and practical aspects of branching process theory. Further, they amply demonstrate that the theoretical research in this area remains vital and topical, as well as the relevance of branching concepts in the development of theoretical approaches to solving new problems in applied fields such as Epidemiology, Biology, Genetics, and, of course, Population Dynamics. The topics covered can broadly be classified into the following areas: 1. Coalescent Branching Processes 2. Branching Random Walks 3. Population Growth Models in Varying and Random Environments 4. Size/Density/Resource-Dependent Branching Models 5. Age-Dependent Branching Models 6. Special Branching Models 7. Applications in Epidemiology 8. Applications in Biology and Genetics Offer...

Weak radiative decays of the B meson and bounds on M{sub H}± in the Two-Higgs-Doublet Model

Energy Technology Data Exchange (ETDEWEB)

Misiak, Mikolaj [University of Warsaw, Faculty of Physics, Institute of Theoretical Physics, Warsaw (Poland); CERN, Theoretical Physics Department, Geneva 23 (Switzerland); Steinhauser, Matthias [Karlsruhe Institute of Technology (KIT), Institut fuer Theoretische Teilchenphysik, Karlsruhe (Germany)

2017-03-15

In a recent publication (Abdesselam et al. arXiv:1608.02344), the Belle collaboration updated their analysis of the inclusive weak radiative B-meson decay, including the full dataset of (772 ± 11) x 10{sup 6} B anti B pairs. Their result for the branching ratio is now below the Standard Model prediction (Misiak et al. Phys Rev Lett 114:221801, 2015, Czakon et al. JHEP 1504:168, 2015), though it remains consistent with it. However, bounds on the charged Higgs boson mass in the Two-Higgs-Doublet Model get affected in a significant manner. In the so-called Model II, the 95% C.L. lower bound on M{sub H}± is now in the 570-800 GeV range, depending quite sensitively on the method applied for its determination. Our present note is devoted to presenting and discussing the updated bounds, as well as to clarifying several ambiguities that one might encounter in evaluating them. One of such ambiguities stems from the photon energy cutoff choice, which deserves re-consideration in view of the improved experimental accuracy. (orig.)

Upper Bound for Queue length in Regulated Burst Service Scheduling

Directory of Open Access Journals (Sweden)

Mahmood Daneshvar Farzanegan

2016-01-01

Full Text Available Quality of Service (QoS provisioning is very important in next computer/communication networks because of increasing multimedia services. Hence, very investigations are performed in this area. Scheduling algorithms effect QoS provisioning. Lately, a scheduling algorithm called Regulated Burst Service Scheduling (RBSS suggested by author in [1] to provide a better service to bursty and delay sensitive services such as video. One of the most significant feature in RBSS is considering burstiness of arrival traffic in scheduling algorithm. In this paper, an upper bound of queue length or buffer size and service curve are calculated by Network Calculus analysis for RBSS. Because in RBSS queue length is a parameter that is considered in scheduling arbitrator, analysis results a differential inequality to obtain service curve. To simplify, arrival traffic is assumed to be linear that is defined in the paper clearly. This paper help to analysis delay in RBSS for different traffic with different specifications. Therefore, QoS provisioning will be evaluated.

Poisson branching point processes

International Nuclear Information System (INIS)

Matsuo, K.; Teich, M.C.; Saleh, B.E.A.

1984-01-01

We investigate the statistical properties of a special branching point process. The initial process is assumed to be a homogeneous Poisson point process (HPP). The initiating events at each branching stage are carried forward to the following stage. In addition, each initiating event independently contributes a nonstationary Poisson point process (whose rate is a specified function) located at that point. The additional contributions from all points of a given stage constitute a doubly stochastic Poisson point process (DSPP) whose rate is a filtered version of the initiating point process at that stage. The process studied is a generalization of a Poisson branching process in which random time delays are permitted in the generation of events. Particular attention is given to the limit in which the number of branching stages is infinite while the average number of added events per event of the previous stage is infinitesimal. In the special case when the branching is instantaneous this limit of continuous branching corresponds to the well-known Yule--Furry process with an initial Poisson population. The Poisson branching point process provides a useful description for many problems in various scientific disciplines, such as the behavior of electron multipliers, neutron chain reactions, and cosmic ray showers

SPECIAL LIBRARIES OF FRAGMENTS OF ALGORITHMIC NETWORKS TO AUTOMATE THE DEVELOPMENT OF ALGORITHMIC MODELS

Directory of Open Access Journals (Sweden)

V. E. Marley

2015-01-01

Full Text Available Summary. The concept of algorithmic models appeared from the algorithmic approach in which the simulated object, the phenomenon appears in the form of process, subject to strict rules of the algorithm, which placed the process of operation of the facility. Under the algorithmic model is the formalized description of the scenario subject specialist for the simulated process, the structure of which is comparable with the structure of the causal and temporal relationships between events of the process being modeled, together with all information necessary for its software implementation. To represent the structure of algorithmic models used algorithmic network. Normally, they were defined as loaded finite directed graph, the vertices which are mapped to operators and arcs are variables, bound by operators. The language of algorithmic networks has great features, the algorithms that it can display indifference the class of all random algorithms. In existing systems, automation modeling based on algorithmic nets, mainly used by operators working with real numbers. Although this reduces their ability, but enough for modeling a wide class of problems related to economy, environment, transport, technical processes. The task of modeling the execution of schedules and network diagrams is relevant and useful. There are many counting systems, network graphs, however, the monitoring process based analysis of gaps and terms of graphs, no analysis of prediction execution schedule or schedules. The library is designed to build similar predictive models. Specifying source data to obtain a set of projections from which to choose one and take it for a new plan.