Branch and Bound Algorithm for Multiprocessor Scheduling
Rahman, Mostafizur
2009-01-01
The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound...
An ellipsoidal branch and bound algorithm for global optimization
Hager, William; Phan, Dzung
2009-01-01
A branch and bound algorithm is developed for global optimization. Branching in the algorithm is accomplished by subdividing the feasible set using ellipses. Lower bounds are obtained by replacing the concave part of the objective function by an affine underestimate. A ball approximation algorithm, obtained by generalizing of a scheme of Lin and Han, is used to solve the convex relaxation of the original problem. The ball approximation algorithm is compared to SEDUMI as well as to gradient pr...
Towards a taxonomy of parallel branch and bound algorithms
Trienekens, H.W.J.M.; Bruin, Arie
1992-01-01
textabstractIn this paper we present a classification of parallel branch and bound algorithms, and elaborate on the consequences of particular parameter settings. The taxonomy is based upon how the algorithms handle the knowledge about the problem instance to be solved, generated during execution. The starting point of the taxonomy is the generally accepted description of the sequential branch and bound algorithm, as presented in, for example, [Mitten 1970] and [Ibaraki 1976a, 1976b, 1977a, 1...
Kodiak: An Implementation Framework for Branch and Bound Algorithms
Smith, Andrew P.; Munoz, Cesar A.; Narkawicz, Anthony J.; Markevicius, Mantas
2015-01-01
Recursive branch and bound algorithms are often used to refine and isolate solutions to several classes of global optimization problems. A rigorous computation framework for the solution of systems of equations and inequalities involving nonlinear real arithmetic over hyper-rectangular variable and parameter domains is presented. It is derived from a generic branch and bound algorithm that has been formally verified, and utilizes self-validating enclosure methods, namely interval arithmetic and, for polynomials and rational functions, Bernstein expansion. Since bounds computed by these enclosure methods are sound, this approach may be used reliably in software verification tools. Advantage is taken of the partial derivatives of the constraint functions involved in the system, firstly to reduce the branching factor by the use of bisection heuristics and secondly to permit the computation of bifurcation sets for systems of ordinary differential equations. The associated software development, Kodiak, is presented, along with examples of three different branch and bound problem types it implements.
Initialization of parallel branch-and-bound algorithms
Henrich, Dominik
1993-01-01
Four different initialization methods for parallel Branch-and-bound algorithms are described and compared with reference to several criteria. A formal analysis of their idle times and efficiency follows. It indicates that the efficiency of three methods depends on the branching factor of the search tree. Furthermore, the fourth method offers the best efficiency of the overall algorithm when a centralized OPEN set is used. Experimental results by a PRAM simulation support these statements.
A Simplicial Branch and Bound Duality-Bounds Algorithm to Linear Multiplicative Programming
Xue-Gang Zhou; Bing-Yuan Cao
2013-01-01
A simplicial branch and bound duality-bounds algorithm is presented to globally solving the linear multiplicative programming (LMP). We firstly convert the problem (LMP) into an equivalent programming one by introducing $p$ auxiliary variables. During the branch and bound search, the required lower bounds are computed by solving ordinary linear programming problems derived by using a Lagrangian duality theory. The proposed algorithm proves that it is convergent to a global mini...
Computing real zeros of a polynomial by branch and bound and branch and reduce algorithms
Directory of Open Access Journals (Sweden)
Le Thi Hoai An
2014-01-01
Full Text Available In this paper we propose two algorithms based on branch and bound method and reduced interval techniques to compute all real zeros of a polynomial. Quadratic bounding functions are proposed which are better than the well known linear underestimator. Experimental result shows the efficiency of the two algorithms when facing ill-conditioned polynomials.
An Effective Branch and Bound Algorithm for Minimax Linear Fractional Programming
Hong-Wei Jiao; Feng-Hui Wang; Yong-Qiang Chen
2014-01-01
An effective branch and bound algorithm is proposed for globally solving minimax linear fractional programming problem (MLFP). In this algorithm, the lower bounds are computed during the branch and bound search by solving a sequence of linear relaxation programming problems (LRP) of the problem (MLFP), which can be derived by using a new linear relaxation bounding technique, and which can be effectively solved by the simplex method. The proposed branch and bound algorithm is convergent to the...
A Branch and Bound Algorithm for the Global Optimization of Hessian Lipschitz Continuous Functions
Fowkes, J. M.; Gould, N. I. M.; Farmer, C.L.
2012-01-01
We present a branch and bound algorithm for the global optimization of a twice differentiable nonconvex objective function with a Lipschitz continuous Hessian over a compact, convex set. The algorithm is based on applying cubic regularisation techniques to the objective function within an overlapping branch and bound algorithm for convex constrained global optimization. Unlike other branch and bound algorithms, lower bounds are obtained via nonconvex underestimators of the function. For a num...
A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions
Fowkes, Jaroslav M.
2012-06-21
We present a branch and bound algorithm for the global optimization of a twice differentiable nonconvex objective function with a Lipschitz continuous Hessian over a compact, convex set. The algorithm is based on applying cubic regularisation techniques to the objective function within an overlapping branch and bound algorithm for convex constrained global optimization. Unlike other branch and bound algorithms, lower bounds are obtained via nonconvex underestimators of the function. For a numerical example, we apply the proposed branch and bound algorithm to radial basis function approximations. © 2012 Springer Science+Business Media, LLC.
Revisiting the upper bounding process in a safe Branch and Bound algorithm
Goldsztejn, Alexandre; Lebbah, Yahia; Michel, Claude; Rueher, Michel
2008-01-01
Finding feasible points for which the proof succeeds is a critical issue in safe Branch and Bound algorithms which handle continuous problems. In this paper, we introduce a new strategy to compute very accurate approximations of feasible points. This strategy takes advantage of the Newton method for under-constrained systems of equations and inequalities. More precisely, it exploits the optimal solution of a linear relaxation of the problem to compute efficiently a promising upper bound. Firs...
Parallel Branch and Bound Algorithm for Computing Maximal Structured Singular Value
Chen, Xinjia; Zhou, Kemin
2008-01-01
In this paper, we have developed a parallel branch and bound algorithm which computes the maximal structured singular value $\\mu$ without tightly bounding $\\mu$ for each frequency and thus significantly reduce the computational complexity.
Revisiting the upper bounding process in a safe Branch and Bound algorithm
Goldsztejn, Alexandre; Michel, Claude; Rueher, Michel
2008-01-01
Finding feasible points for which the proof succeeds is a critical issue in safe Branch and Bound algorithms which handle continuous problems. In this paper, we introduce a new strategy to compute very accurate approximations of feasible points. This strategy takes advantage of the Newton method for under-constrained systems of equations and inequalities. More precisely, it exploits the optimal solution of a linear relaxation of the problem to compute efficiently a promising upper bound. First experiments on the Coconuts benchmarks demonstrate that this approach is very effective.
Branch and bound algorithms for rate-distortion optimized media streaming
Röder, Martin; Cardinal, Jean; Hamzaoui, Raouf
2006-01-01
We consider the problem of ratedistortion optimized streaming of packetized multimedia data over a single quality of service network using feedback and retransmissions. For a single data unit, we prove that the problem is NP-hardand provide efficient branch and bound algorithms that are much faster than the previously best solution based on dynamic programming. For a group of interdependent data units, we show how to compute optimal solutions with branch and bound algorithms. The branch and b...
A new branch and bound algorithm for the network design problem
G. Gallo
1981-01-01
A Branch and Bound algorithm is presented to solve the Network Design Problem. This algorithm makes use of new upper and lower bounds which are sharper than the ones used in previous algorithms of the same type. The results of a rather wide numerical experimentation are illustrated.
An Enhanced Branch-and-bound Algorithm for the Talent Scheduling Problem
Zhang, Zizhen; Qin, Hu; Liang, Xiaocong; Lim, Andrew
2014-01-01
The talent scheduling problem is a simplified version of the real-world film shooting problem, which aims to determine a shooting sequence so as to minimize the total cost of the actors involved. In this article, we first formulate the problem as an integer linear programming model. Next, we devise a branch-and-bound algorithm to solve the problem. The branch-and-bound algorithm is enhanced by several accelerating techniques, including preprocessing, dominance rules and caching search states....
A Branch and Bound Reduced Algorithm for Quadratic Programming Problems with Quadratic Constraints
Yuelin Gao; Feifei Li; Siqiao Jin
2013-01-01
We propose a branch and bound reduced algorithm for quadratic programming problems with quadratic constraints. In this algorithm, we determine the lower bound of the optimal value of original problem by constructing a linear relaxation programming problem. At the same time, in order to improve the degree of approximation and the convergence rate of acceleration, a rectangular reduction strategy is used in the algorithm. Numerical experiments show that the proposed algorithm is feasible and ef...
A Branch and Bound Algorithm for Project Scheduling Problem with Spatial Resource Constraints
Shicheng Hu; Song Wang; Yonggui Kao; Takao Ito; Xuedong Sun
2015-01-01
With respect to the block assembly schedule in a shipbuilding enterprise, a spatial resource constrained project scheduling problem (SRCPSP) is proposed, which aims to minimize the makespan of a project under the constraints of the availability of a two-dimensional spatial resource and the precedence relationship between tasks. In order to solve SRCPSP to the optimum, a branch and bound algorithm (BB) is developed. For the BB-SRCPSP, first, an implicitly enumerative branch scheme is presented...
Brusco, Michael J.
2002-01-01
Developed a branch-and-bound algorithm that can be used to seriate a symmetric dissimilarity matrix by identifying a reordering of rows and columns of the matrix optimizing an anti-Robinson criterion. Computational results suggest that with respect to computational efficiency, the approach is generally competitive with dynamic programming. (SLD)
Veldkamp, Bernard P.
A mathematical programming approach is presented for computer adaptive testing (CAT) with many constraints on the item and test attributes. Because mathematical programming problems have to be solved while the examinee waits for the next item, a fast implementation of the Branch-and-Bound algorithm is needed for this approach. Eight modifications…
A branch-and-bound algorithm for stable scheduling in single-machine production systems
Leus, Roel; Herroelen, Willy
2004-01-01
Robust scheduling aims at the construction of a schedule that is protected against uncertain events. A stable schedule is a robust schedule that will change little when variations in the input parameters arise. This paper proposes a branch-and-bound algorithm for optimally solving a single-machine scheduling problem with stability objective, when a single job is anticipated to be disrupted.
Parallel Branch and Bound Algorithm - A comparison between serial, OpenMP and MPI implementations
International Nuclear Information System (INIS)
This paper presents a comparison of an extended version of the regular Branch and Bound algorithm previously implemented in serial with a new parallel implementation, using both MPI (distributed memory parallel model) and OpenMP (shared memory parallel model). The branch-and-bound algorithm is an enumerative optimization technique, where finding a solution to a mixed integer programming (MIP) problem is based on the construction of a tree where nodes represent candidate problems and branches represent the new restrictions to be considered. Through this tree all integer solutions of the feasible region of the problem are listed explicitly or implicitly ensuring that all the optimal solutions will be found. A common approach to solve such problems is to convert sub-problems of the mixed integer problem to linear programming problems, thereby eliminating some of the integer constraints, and then trying to solve that problem using an existing linear program approach. The paper describes the general branch and bound algorithm used and provides details on the implementation and the results of the comparison.
A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks
Maher Rebai; Matthieu Le Berre; Faicel Hnaien; Hichem Snoussi; Lyes Khoukhi
2014-01-01
We aim to cover a grid fully by deploying the necessary wireless sensors while maintaining connectivity between the deployed sensors and a base station (the sink). The problem is NP-Complete as it can be reduced to a 2-dimensional critical coverage problem, which is an NP-Complete problem. We develop a branch and bound (B&B) algorithm to solve the problem optimally. We verify by computational experiments that the proposed B&B algorithm is more efficient, in terms of computation time, than the...
M Barketau; Kopfer, H; E. Pesch
2013-01-01
In this paper, we consider the container transshipment problem at a railway hub. A simple lower bound known for this problem will be improved by a new Lagrangian relaxation lower bound. Computational tests show that this lower bound outperforms the simple one and decreases substantially the run time of the branch-and-bound algorithm.
Nakariyakul, Songyot; Casasent, David
2006-10-01
Detection of skin tumors on chicken carcasses is considered. A chicken skin tumor consists of an ulcerous lesion region surrounded by a region of thickened-skin. We use a new adaptive branch-and-bound (ABB) feature selection algorithm to choose only a few useful wavebands from hyperspectral data for use in a real-time multispectral camera. The ABB algorithm selects an optimal feature subset and is shown to be much faster than any other versions of the branch and bound algorithm. We found that the spectral responses of the lesion and the thickened-skin regions of tumors are considerably different; thus we train our feature selection algorithm to separately detect the lesion regions and thickened-skin regions of tumors. We then fuse the two HS detection results of lesion and thickened-skin regions to reduce false alarms. Initial results on six hyperspectral cubes show that our method gives an excellent tumor detection rate and a low false alarm rate.
A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time
Hoogeveen, Han; Velde, Steef
1996-01-01
textabstractPresents a branch-and-bound algorithm which is based upon many dominance rules and various lower bound approaches, including relaxation of the machine capacity, data manipulation and Lagrangian relaxation. Insertion of the idle time for a given sequence; Properties of the proposed lower bounds.
A Parallel Branch and Bound Algorithm for the Maximum Labelled Clique Problem
McCreesh, Ciaran; Prosser, Patrick
2014-01-01
The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.
A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs
DEFF Research Database (Denmark)
Stidsen, Thomas Riis; Andersen, Kim Allan; Dammann, Bernd
2014-01-01
Pareto-optimal front). In this paper, we first give a survey of the newly developed branch and bound methods for solving MOMIP problems. After that, we propose a new branch and bound method for solving a subclass of MOMIP problems, where only two objectives are allowed, the integer variables are binary......, and one of the two objectives has only integer variables. The proposed method is able to find the full set of nondominated points. It is tested on a large number of problem instances, from six different classes of MOMIP problems. The results reveal that the developed biobjective branch and bound...
Institute of Scientific and Technical Information of China (English)
Belgacem BETTAYEB; Imed KACEM; Kondo H.ADJALLAH
2008-01-01
This article investigates identical parallel machines scheduling with family setup times. Theobjective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.
A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs
DEFF Research Database (Denmark)
Stidsen, Thomas Riis; Andersen, Kim Allan; Dammann, Bernd
2014-01-01
Pareto-optimal front). In this paper, we first give a survey of the newly developed branch and bound methods for solving MOMIP problems. After that, we propose a new branch and bound method for solving a subclass of MOMIP problems, where only two objectives are allowed, the integer variables are binary......, and one of the two objectives has only integer variables. The proposed method is able to find the full set of nondominated points. It is tested on a large number of problem instances, from six different classes of MOMIP problems. The results reveal that the developed biobjective branch and bound...... method performs better on five of the six test problems, compared with a generic two-phase method. At this time, the two-phase method is the most preferred exact method for solving MOMIP problems with two criteria and binary variables....
A Lagrangian Dual-Based Branch-and-Bound Algorithm for the Generalized Multi-Assignment Problem
June S. Park; Byung Ha Lim; Youngho Lee
1998-01-01
This paper develops a Lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem (GMAP) which includes the well-known generalized assignment problem (GAP) as a special case. In GMAP, an object may be required to be duplicated in multiple locations. We develop a Lagrangian dual ascent algorithm for GMAP. This dual ascent and the subgradient search each possess advantages that can be combined to develop a new Lagrangian dual search algorithm. The latter algori...
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...
A subgradient-based branch-and-bound algorithm for the capacitated facility location problem
DEFF Research Database (Denmark)
Görtz, Simon; Klose, Andreas
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. In order 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 more faster and robust than other state-of-the-art methods for solving the CFLP exactly....
On prediction mechanisms in Fast Branch & Bound algorithms
Czech Academy of Sciences Publication Activity Database
Somol, Petr; Pudil, Pavel; Grim, Jiří
Berlin : Springer, 2004 - (Fred, A.; Caelli, T.; Duin, R.), s. 716-724 ISBN 3-540-22570-6. - (Lecture Notes in Computer Science.. 3138). [Joint IAPR Workshops SSPR 2004 and SPR 2004. Lisbon (PT), 18.08.2004-20.08.2004] R&D Projects: GA ČR GA402/02/1271; GA ČR GA402/03/1310 Institutional research plan: CEZ:AV0Z1075907 Keywords : subset search * feature selection * search tree Subject RIV: BD - Theory of Information http://library.utia.cas.cz/separaty/historie/somol-on prediction mechanisms in fast branch & bound algorithms.pdf
Towards an abstract parallel branch and bound machine
Bruin, Arie; Kindervater, Gerard; Trienekens, H.W.J.M.
1995-01-01
textabstractMany (parallel) branch and bound algorithms look very different from each other at first glance. They exploit, however, the same underlying computational model. This phenomenon can be used to define branch and bound algorithms in terms of a set of basic rules that are applied in a specific (predefined) order. In the sequential case, the specification of Mitten's rules turns out to be sufficient for the development of branch and bound algorithms. In the parallel case, the situation...
Directory of Open Access Journals (Sweden)
Shangchia Liu
2015-01-01
Full Text Available In the field of distributed decision making, different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. These issues arise in different application contexts, including real-time systems, integrated service networks, industrial districts, and telecommunication systems. Motivated by its importance on practical applications, we consider two-agent scheduling on a single machine where the objective is to minimize the total completion time of the jobs of the first agent with the restriction that an upper bound is allowed the total completion time of the jobs for the second agent. For solving the proposed problem, a branch-and-bound and three simulated annealing algorithms are developed for the optimal solution, respectively. In addition, the extensive computational experiments are also conducted to test the performance of the algorithms.
Combining Interval Branch and Bound and Stochastic Search
Dhiranuch Bunnag
2014-01-01
This paper presents global optimization algorithms that incorporate the idea of an interval branch and bound and the stochastic search algorithms. Two algorithms for unconstrained problems are proposed, the hybrid interval simulated annealing and the combined interval branch and bound and genetic algorithm. The numerical experiment shows better results compared to Hansen’s algorithm and simulated annealing in terms of the storage, speed, and number of function evaluations. The convergence pro...
An object oriented approach to generic branch and bound
Bruin, Arie; Kindervater, Gerard; Trienekens, H.W.J.M.; Goot, R.A.
1996-01-01
textabstractBranch and bound algorithms can be characterized by a small set of basic rules that are applied in a divide-and-conquer-like framework. The framework is about the same in all applications, whereas the specification of the rules is problem dependent. Building a framework is a rather simple task in sequential implementations, but must not be underestimated in the parallel case, especially if an efficient branch and bound algorithm is required. In generic branch and bound models, the...
Distribution Network Planning and Design Using Branch and Bound Methods
Jalal Abdallah
2005-01-01
This study presents implementation of the bound and branch methods as an optimization mathematical device for distribution network planning. A development technology concentrates on minimizing the total costs and provides extended opportunities for improvement of network operation, from the initial planning stage. The study illustrate the mathematical and the algorithm of the branch and bound method with an example to indicate the efficiency of the branch and bound in plan...
Distribution Network Planning and Design Using Branch and Bound Methods
Directory of Open Access Journals (Sweden)
Jalal Abdallah
2005-01-01
Full Text Available This study presents implementation of the bound and branch methods as an optimization mathematical device for distribution network planning. A development technology concentrates on minimizing the total costs and provides extended opportunities for improvement of network operation, from the initial planning stage. The study illustrate the mathematical and the algorithm of the branch and bound method with an example to indicate the efficiency of the branch and bound in planning and design processes. It also shows that the optimal configuration strongly depends on the branching rule and on the bound calculation bases.
Improved branch and bound method for control structure screening
Cao, Yi; Saha, Prabirkumar
2005-01-01
The main aim of this paper is to present an improved algorithm of “Branch and Bound” method for control structure screening. The new algorithm uses a best- first search approach, which is more efficient than other algorithms based on depth-first search approaches. Detailed explanation of the algorithms is provided in this paper along with a case study on Tennessee–Eastman process to justify the theory of branch and bound method. The case study uses the Hankel singular value ...
Muu, Lê D.; Oettli, Werner
1988-01-01
A unifled approach to branch-and-bound and cutting plane methods for solving a certain class of nonconvex optimization problems is proposed. Based on this approach an implementable algorithm is obtained for programming problems with a bilinear objective function and jointly convex constraints.
A branch and bound algorithm to optimize the representation of tabular decision processe
Vanthienen, Jan; Dries, E
1996-01-01
Decision situations have various aspects: knowledge acquisition and structuring, knowledge representation, knowledge validation and decision making. It has been recognized in literature that decision tables can play an important role in each of these stages. It is however not necessary to use only one representation formalism during the whole life cycle of an intelligent system. Likewise it is possible that different formats of the same formalism serve different purposes in the development...
A Branch and Bound Method for Optimization Problems with Fuzzy Numbers
Iemets, O.; Yemets, O.
2012-01-01
The algorithm of branch and bound method for the minimization problem in the fuzzy setting is proposed. The use of branch and bound method for combinatorial transportation problem on permutations with fuzzy data is shown.
Basis Reduction, and the Complexity of Branch-and-Bound
Pataki, Gabor; Tural, Mustafa
2009-01-01
The classical branch-and-bound algorithm for the integer feasibility problem has exponential worst case complexity. We prove that it is surprisingly efficient on reformulated problems, in which the columns of the constraint matrix are short, and near orthogonal, i.e. a reduced basis of the generated lattice; when the entries of A (the dense part of the constraint matrix) are from {1, ..., M} for a large enough M, branch-and-bound solves almost all reformulated instances at the rootnode. We al...
Branch and Bound Experiments in Convex Nonlinear Integer Programming
Omprakash K. Gupta; Ravindran, A
1985-01-01
The branch and bound principle has long been established as an effective computational tool for solving mixed integer linear programming problems. This paper investigates the computational feasibility of branch and bound methods in solving convex nonlinear integer programming problems. The efficiency of a branch and bound method often depends on the rules used for selecting the branching variables and branching nodes. Among others, the concepts of pseudo-costs and estimations are implemented ...
Solving Multistage Influence Diagrams using Branch-and-Bound Search
Yuan, Changhe; Wu, Xiaojian; Hansen, Eric A.
2012-01-01
A branch-and-bound approach to solving influ- ence diagrams has been previously proposed in the literature, but appears to have never been implemented and evaluated - apparently due to the difficulties of computing effective bounds for the branch-and-bound search. In this paper, we describe how to efficiently compute effective bounds, and we develop a practical implementa- tion of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solvin...
A Branch and Bound and Simulated Annealing Approach for Job Shop Scheduling
Tan Hui Woon; Sutinah Salim
2004-01-01
This paper presents two approaches to the solution of the job shop scheduling problem, namely the branch and bound, and simulated annealing approach. The objective is to schedule the jobs on the machines so that the total completion time is minimized. In the branch and bound approach, the job shop scheduling problem is represented by a disjunctive graph, then the optimal schedule is obtained using the branch and bound algorithm while simulated annealing is a local search based algorithm which...
Faster Algorithms on Branch and Clique Decompositions
Bodlaender, Hans L.; van Leeuwen, Erik Jan; van Rooij, Johan M. M.; Vatshelle, Martin
We combine two techniques recently introduced to obtain faster dynamic programming algorithms for optimization problems on graph decompositions. The unification of generalized fast subset convolution and fast matrix multiplication yields significant improvements to the running time of previous algorithms for several optimization problems. As an example, we give an O^{*}(3^{ω/2k}) time algorithm for Minimum Dominating Set on graphs of branchwidth k, improving on the previous O *(4 k ) algorithm. Here ω is the exponent in the running time of the best matrix multiplication algorithm (currently ωgraphs of cliquewidth k, we improve from O *(8 k ) to O *(4 k ). We also obtain an algorithm for counting the number of perfect matchings of a graph, given a branch decomposition of width k, that runs in time O^{*}(2^{ω/2k}). Generalizing these approaches, we obtain faster algorithms for all so-called [ρ,σ]-domination problems on branch decompositions if ρ and σ are finite or cofinite. The algorithms presented in this paper either attain or are very close to natural lower bounds for these problems.
PICO: An Object-Oriented Framework for Branch and Bound
Energy Technology Data Exchange (ETDEWEB)
ECKSTEIN,JONATHAN; HART,WILLIAM E.; PHILLIPS,CYNTHIA A.
2000-12-01
This report describes the design of PICO, a C++ framework for implementing general parallel branch-and-bound algorithms. The PICO framework provides a mechanism for the efficient implementation of a wide range of branch-and-bound methods on an equally wide range of parallel computing platforms. We first discuss the basic architecture of PICO, including the application class hierarchy and the package's serial and parallel layers. We next describe the design of the serial layer, and its central notion of manipulating subproblem states. Then, we discuss the design of the parallel layer, which includes flexible processor clustering and communication rates, various load balancing mechanisms, and a non-preemptive task scheduler running on each processor. We describe the application of the package to a branch-and-bound method for mixed integer programming, along with computational results on the ASCI Red massively parallel computer. Finally we describe the application of the branch-and-bound mixed-integer programming code to a resource constrained project scheduling problem for Pantex.
Parallel Branch and Bound on a CPU-GPU System
Boukedjar, Abdelamine; Lalami, Mohamed Esseghir; El-Baz, Didier
2012-01-01
Hybrid implementation via CUDA of a branch and bound method for knapsack problems is proposed. Branch and bound computations can be carried out either on the CPU or on the GPU according to the size of the branch and bound list, i.e. the number of nodes. Tests are carried out on a Tesla C2050 GPU. A first series of computational results showing a substantial speedup is displayed and analyzed.
A branch-and-bound methodology within algebraic modelling systems
Bisschop, J.J.; Heerink, J.B.J.; Kloosterman, G.
1998-01-01
Through the use of application-specific branch-and-bound directives it is possible to find solutions to combinatorial models that would otherwise be difficult or impossible to find by just using generic branch-and-bound techniques within the framework of mathematical programming. {\\sc Minto} is an example of a system which offers the possibility to incorporate user-provided directives (written in {\\sc C}) to guide the branch-and-bound search. Its main focus, however, remains on mathematical p...
A Branch and Bound Approach to Solve the Preemptive Resource Leveling Problem
Behrouz Afshar-Nadjafi; Zeinab Khalaj; Esmaeil Mehdizadeh
2013-01-01
We study resource constrained project scheduling problem with respect to resource leveling as objective function and allowance of preemption in activities. The branch and bound algorithms proposed in previous researches on resource leveling problem do not consider preemption. So, representing a model for the problem, a branch and bound algorithm is proposed. This algorithm can handle preemption in resource leveling problem. Comparing the resource leveling problem and the preemptive resource l...
Metode Branch And Bound Untuk Menyelesaikan Program Stokastik Integer Dengan Adanya Resiko
Pangaribuan, Adil H.
2011-01-01
This thesis is addressed to develop branch-and-bound methods, that is to solve multistage stochastic integer programs with risk objectives which is related to wait-and-see problems which could be separated like risk neutral. All model classi_ed to this is overcome by presenting a combination between branch-and-bound algorithm and relaxation of non-anticipativity and constraint branching along non-anticipativity subspaces.
A parametric branch and bound approach to suboptimal explicit hybrid MPC
Axehill, Daniel; Besselmann, Thomas; Martino Raimondo, Davide; Morari, Manfred
2014-01-01
In this article we present a parametric branch and bound algorithm for computation of optimal and suboptimal solutions to parametric mixed-integer quadratic programs and parametric mixed-integer linear programs. The algorithm returns an optimal or suboptimal parametric solution with the level of suboptimality requested by the user. An interesting application of the proposed parametric branch and bound procedure is suboptimal explicit MPC for hybrid systems, where the introduced user-defined s...
Improved Branch-and-Bound for Low Autocorrelation Binary Sequences
Prestwich, S. D.
2013-01-01
The Low Autocorrelation Binary Sequence problem has applications in telecommunications, is of theoretical interest to physicists, and has inspired many optimisation researchers. Metaheuristics for the problem have progressed greatly in recent years but complete search has not progressed since a branch-and-bound method of 1996. In this paper we find four ways of improving branch-and-bound, leading to a tighter relaxation, faster convergence to optimality, and better empirical scalability.
PENJADWALAN PRODUKSI DENGAN METODE BRANCH AND BOUND PADA PT. XYZ
Mangngenre, Saiful; Rapi, Amrin; Flannery, Wendy
2014-01-01
Penjadwalan adalah suatu proses pengalokasian sumber daya dan mesin yang tersedia untuk menyelesaikan suatu pekerjaan dengan mempertimbangkan batasan-batasan yang ada.Penjadwalan produksi yang diterapkan di PT. XYZ selama ini hanya menggunakan metode intuitif saja. Dalam penelitian ini, untuk memecahkan masalah penjadwalan maka digunakan metode Branch and Bound. Metode Branch and Bound adalah metode pencarian solusi optimal pada permasalahan optimasi seperti pada masalah penjadwalan dengan ...
Branch and peg algorithms for the simple plant location problem
Goldengorin, Boris; Ghosh, Diptesh; Sierksma, Gerard
2001-01-01
The simple plant location problem is a well-studied problem in combinatorial optimization. It is one of deciding where to locate a set of plants so that a set of clients can be supplied by them at the minimum cost. This problem of ten appears as a subproblem in other combinatorial problems. Several branch and bound techniques have been developed to solve these problems. In this paper we present a few techniques that enhance the performance of branch and bound algorithms. The new algorithms th...
Fernandes, Florbela P.; Costa, Fernanda P.M.; Fernandes, Edite M.G.P.
2014-01-01
A mixed-integer nonlinear programming problem (MINLP) is a problem with continuous and integer variables and at least, one nonlinear function. This kind of problem appears in a wide range of real applications and is very difficult to solve. The difficulties are due to the nonlinearities of the functions in the problem and the integrality restrictions on some variables. When they are nonconvex then they are the most difficult to solve above all. We present a methodology to solve nonsmooth no...
Branch and Bound Methods for a Search Problem
Washburn, Alan R.
1997-01-01
The problem of searching for randomly moving targets such as children and submarines is known to be fundamentally difficult, but finding efficient methods for generating optimal or near optimal solutions is nonetheless an important practical problem. This paper investigates the efficiency of Branch and Bound methods, with emphasis on the tradeoff between the accuracy of the bound employed and the time required to compute it. A variety of bounds are investigated, some of which a...
A Branch and Bound Method for Stochastic Global Optimization
V.I. Norkin; G.C. Pflug; Ruszczynski, A.
1996-01-01
A stochastic version of the branch and bound method is proposed for solving stochastic global optimization problems. The method, instead of deterministic bounds, uses stochastic upper and lower estimates of the optimal value of subproblems, to guide the partitioning process. Almost sure convergence of the method is proved and random accuracy estimates derived. Methods for constructing random bounds for stochastic global optimization problems are discussed. The theoretical considerations are i...
Design of planar articulated mechanisms using branch and bound
DEFF Research Database (Denmark)
Stolpe, Mathias; Kawamoto, Atsushi
2005-01-01
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...... convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve...
Design of planar articulated mechanisms using branch and bound
DEFF Research Database (Denmark)
Stolpe, Mathias; Kawamoto, Atsushi
2004-01-01
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...... convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve...
Doyon, Jean-Philippe; Chauve, Cedric
2010-01-01
We describe a Branch-and-Bound algorithm for computing a parsimonious species tree given a set of gene family trees. Our algorithm can compute a parsimonious species tree for three cost measures: number of gene duplications, number of gene losses, and both combined. Moreover, to cope with intrinsic limitations of Branch-and-Bound algorithms for species trees inference regarding the number of taxa that can be considered, our algorithm can naturally take into account predefined relationships be...
Recursive algorithms, branching coefficients and applications
Lyakhovsky, Vladimir
2010-01-01
Recurrent relations for branching coefficients in affine Lie algebras integrable highest weight modules are studied. The decomposition algorithm based on the injection fan technique is adopted to the situation where the Weyl denominator becomes singular with respect to a reductive subalgebra. We study some modifications of the injection fan technique and demonstrate that it is possible to define the "subtracted fans" that play the role similar to the original ones. Possible applications of subtracted fans in CFT models are considered.
Computational Protein Design Using AND/OR Branch-and-Bound Search.
Zhou, Yichao; Wu, Yuexin; Zeng, Jianyang
2016-06-01
The computation of the global minimum energy conformation (GMEC) is an important and challenging topic in structure-based computational protein design. In this article, we propose a new protein design algorithm based on the AND/OR branch-and-bound (AOBB) search, a variant of the traditional branch-and-bound search algorithm, to solve this combinatorial optimization problem. By integrating with a powerful heuristic function, AOBB is able to fully exploit the graph structure of the underlying residue interaction network of a backbone template to significantly accelerate the design process. Tests on real protein data show that our new protein design algorithm is able to solve many problems that were previously unsolvable by the traditional exact search algorithms, and for the problems that can be solved with traditional provable algorithms, our new method can provide a large speedup by several orders of magnitude while still guaranteeing to find the global minimum energy conformation (GMEC) solution. PMID:27167301
N D
2009-01-01
There has been a lot of recent work on Bayesian methods for reinforcement learning exhibiting near-optimal online performance. The main obstacle facing such methods is that in most problems of interest, the optimal solution involves planning in an infinitely large tree. However, it is possible to obtain stochastic lower and upper bounds on the value of each tree node. This enables us to use stochastic branch and bound algorithms to search the tree efficiently. This paper proposes two such alg...
A branch and bound approach for minimizing the energy consumption of an electrical vehicle
Merakeb, Abdelkader; Messine, Frédéric
2013-01-01
National audience In this paper we discuss about the way to approximate the solution of an optimal control problem with a switched command. Our Method is based on a discretization technique associated with a Branch and Bound algorithm. The problem that we focus on is the minimization of the consumption of the energy of an electrical vehicle during some imposed displacements.
Some distance bounds of branching processes and their diffusion limits
Kammerer, Niels B
2010-01-01
We compute exact values respectively bounds of "distances" - in the sense of (transforms of) power divergences and relative entropy - between two discrete-time Galton-Watson branching processes with immigration GWI for which the offspring as well as the immigration is arbitrarily Poisson-distributed (leading to arbitrary type of criticality). Implications for asymptotic distinguishability behaviour in terms of contiguity and entire separation of the involved GWI are given, too. Furthermore, we determine the corresponding limit quantities for the context in which the two GWI converge to Feller-type branching diffusion processes, as the time-lags between observations tend to zero. Some applications to (static random environment like) Bayesian decision making and Neyman-Pearson testing are presented as well.
Optimal material selection using branch and bound techniques
Sepulveda, A. E.
1993-01-01
A methodology for structural synthesis is presented in which the optimal material selection for the structural members is treated in terms of (0,1) variables. Structural member sizes and material selection variables are treated simultaneously as design variables. Optimization is carried out by generating and solving a sequence of explicit approximate problems using a branch and bound strategy. Intermediate design variables and intermediate response quantities are used to enhance the quality of the approximate design problems. Numerical results for example problems are presented to illustrate the efficiency of the design procedure set forth.
Globally Optimal Hand-Eye Calibration Using Branch-and-Bound.
Heller, Jan; Havlena, Michal; Pajdla, Tomas
2016-05-01
This paper introduces a novel solution to the hand-eye calibration problem. It uses camera measurements directly and, at the same time, requires neither prior knowledge of the external camera calibrations nor a known calibration target. Our algorithm uses branch-and-bound approach to minimize an objective function based on the epipolar constraint. Further, it employs Linear Programming to decide the bounding step of the algorithm.Our technique is able to recover both the unknown rotation and translation simultaneously and the solution is guaranteed to be globally optimal with respect to the L∞-norm. PMID:26353364
A Branch and Bound Method for the Open Shop Problem
Brucker, P; Hurink, J.L.; Jurisch, B.; Wöstmann, B.
1997-01-01
A fast branch & bound method for the open-shop problem based on a disjunctive graph formulation of the problem is developed. Computational results show that the method yields excellent results. Some benchmark problems from the literature were solved to optimality for the first time.
Bifurcation Analysis Using Rigorous Branch and Bound Methods
Smith, Andrew P.; Crespo, Luis G.; Munoz, Cesar A.; Lowenberg, Mark H.
2014-01-01
For the study of nonlinear dynamic systems, it is important to locate the equilibria and bifurcations occurring within a specified computational domain. This paper proposes a new approach for solving these problems and compares it to the numerical continuation method. The new approach is based upon branch and bound and utilizes rigorous enclosure techniques to yield outer bounding sets of both the equilibrium and local bifurcation manifolds. These sets, which comprise the union of hyper-rectangles, can be made to be as tight as desired. Sufficient conditions for the existence of equilibrium and bifurcation points taking the form of algebraic inequality constraints in the state-parameter space are used to calculate their enclosures directly. The enclosures for the bifurcation sets can be computed independently of the equilibrium manifold, and are guaranteed to contain all solutions within the computational domain. A further advantage of this method is the ability to compute a near-maximally sized hyper-rectangle of high dimension centered at a fixed parameter-state point whose elements are guaranteed to exclude all bifurcation points. This hyper-rectangle, which requires a global description of the bifurcation manifold within the computational domain, cannot be obtained otherwise. A test case, based on the dynamics of a UAV subject to uncertain center of gravity location, is used to illustrate the efficacy of the method by comparing it with numerical continuation and to evaluate its computational complexity.
A branch and bound method for the job-shop problem with sequence-dependent setup times
Artigues, Christian; Feillet, Dominique
2007-01-01
This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time window...
Using the primal-dual interior point algorithm within the branch-price-and-cut method
Munari, P.; Gondzio, J.
2013-01-01
Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using the primal-dual interior point algorithm. We discuss in detail how to deal with the challenges of using the interior point alg...
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...
Parallel Branch-and-Bound Methods for the Job Shop Scheduling
DEFF Research Database (Denmark)
Clausen, Jens; Perregaard, Michael
1998-01-01
the JSS problem, but with limited success. Even with recent methods, it is still not possible to solve problems substantially larger than 10 machines and 10 jobs. In the current study, we focus on parallel methods for solving JSS problems. We implement two different parallel branch......-and-bound algorithms for JSS on a 16-processor MEIKO computing surface with Intel i860 processors and perform extensive computational testing using classical publicly available benchmark problems. The parallel part of one of the implementations is based on a similar parallel code for quadratic assignment problems...
A semidefinite programming based branch-and-bound framework for the quadratic assignment problem
2014-01-01
The practical approach to calculate an exact solution for a quadratic assignment problem (QAP) via a branch-and-bound framework depends strongly on a "smart" choice of different strategies within the framework, for example the branching strategy, heuristics for the upper bound or relaxations for the lower bound. In the first part of this thesis, we analyze promising old and new semidefinite programming (SDP) relaxations. In particular, we focus on their complexity, the strength of the respect...
Morrison, David R.; Sewell, Edward C.; Sheldon H. Jacobson
2014-01-01
Branch-and-price algorithms combine a branch-and-bound search with an exponentially-sized LP formulation that must be solved via column generation. Unfortunately, the standard branching rules used in branch-and-bound for integer programming interfere with the structure of the column generation routine; therefore, most such algorithms employ alternate branching rules to circumvent this difficulty. This paper shows how a zero-suppressed binary decision diagram (ZDD) can be used to solve the pri...
Upper bound on the number of steps for solving the subset sum problem by the Branch-and-Bound method
Kolpakov, Roman; Posypkin, Mikhail
2015-01-01
We study the computational complexity of one of the particular cases of the knapsack problem: the subset sum problem. For solving this problem we consider one of the basic variants of the Branch-and-Bound method in which any sub-problem is decomposed along the free variable with the maximal weight. By the complexity of solving a problem by the Branch-and-Bound method we mean the number of steps required for solving the problem by this method. In the paper we obtain upper bounds on the complex...
A Partitioning and Bounded Variable Algorithm for Linear Programming
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…
GPU Implementation of the Branch and Bound method for knapsack problems
El-Baz, Didier; El Baz, Didier; Lalami, Mohamed Esseghir
2012-01-01
In this paper, we propose an efficient implementation of the branch and bound method for knapsack problems on a CPU-GPU system via CUDA. Branch and bound computations can be carried out either on the CPU or on a GPU according to the size of the branch and bound list. A better management of GPUs memories, less GPU-CPU communications and better synchronization between GPU threads are proposed in this new implementation in order to increase efficiency. Indeed, a series of computational results i...
A Branch and Bound Approach for Truss Topology Design Problems with Valid Inequalities
International Nuclear Information System (INIS)
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.
Efficient Implementation Of Branch-And-Bound Method On Desktop Grids
Directory of Open Access Journals (Sweden)
Bo Tian
2014-01-01
Full Text Available The Berkeley Open Infrastructure for Network Computing (BOINC is an opensource middleware system for volunteer and desktop grid computing. In this paper we propose BNBTEST, a BOINC version of distributed branch and bound method. The crucial issues of distributed branch-and-bound method are traversing the search tree and loading balance. We developed subtaskspackaging method and three dierent subtasks' distribution strategies to solve these.
Efficient Implementation Of Branch-And-Bound Method On Desktop Grids
Bo Tian; Mikhail Posypkin
2014-01-01
The Berkeley Open Infrastructure for Network Computing (BOINC) is an opensource middleware system for volunteer and desktop grid computing. In this paper we propose BNBTEST, a BOINC version of distributed branch and bound method. The crucial issues of distributed branch-and-bound method are traversing the search tree and loading balance. We developed subtaskspackaging method and three dierent subtasks' distribution strategies to solve these.
Performance analysis of parallel branch and bound search with the hypercube architecture
Mraz, Richard T.
1987-01-01
With the availability of commercial parallel computers, researchers are examining new classes of problems which might benefit from parallel computing. This paper presents results of an investigation of the class of search intensive problems. The specific problem discussed is the Least-Cost Branch and Bound search method of deadline job scheduling. The object-oriented design methodology was used to map the problem into a parallel solution. While the initial design was good for a prototype, the best performance resulted from fine-tuning the algorithm for a specific computer. The experiments analyze the computation time, the speed up over a VAX 11/785, and the load balance of the problem when using loosely coupled multiprocessor system based on the hypercube architecture.
Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms
DEFF Research Database (Denmark)
Brodal, Gerth Stølting; Moruz, Gabriel
) 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...
Recursive Branching Simulated Annealing Algorithm
Bolcar, Matthew; Smith, J. Scott; Aronstein, David
2012-01-01
solution, and the region from which new configurations can be selected shrinks as the search continues. The key difference between these algorithms is that in the SA algorithm, a single path, or trajectory, is taken in parameter space, from the starting point to the globally optimal solution, while in the RBSA algorithm, many trajectories are taken; by exploring multiple regions of the parameter space simultaneously, the algorithm has been shown to converge on the globally optimal solution about an order of magnitude faster than when using conventional algorithms. Novel features of the RBSA algorithm include: 1. More efficient searching of the parameter space due to the branching structure, in which multiple random configurations are generated and multiple promising regions of the parameter space are explored; 2. The implementation of a trust region for each parameter in the parameter space, which provides a natural way of enforcing upper- and lower-bound constraints on the parameters; and 3. The optional use of a constrained gradient- search optimization, performed on the continuous variables around each branch s configuration in parameter space to improve search efficiency by allowing for fast fine-tuning of the continuous variables within the trust region at that configuration point.
Analisis Permasalahan Cutting Stock Satu Dimensi Dengan Metode Branch And Bound
Sitohang, Veronika LS
2011-01-01
Yang menjadi tujuan dalam permasalahan cutting stock adalah meminimumkan sisa potongan sehingga menambah keuntungan perusahaan. Untuk mencapai tujuan yang sedemikian, diperlukan pemotongan pola yang baik, tanpa mengabaikan panjang standard suatu gulungan raw. Metode Branch and Bound dapat digunakan untuk mengoptimalkan keuntungan dalam menentukan pola yang optimal untuk dipotong dengan memperhatikan batasan-batasan yang diberikan. Tulisan ini membahas tentang bagaimana me...
Enhancements of branch and bound methods for the maximal constraint satisfaction problem
Energy Technology Data Exchange (ETDEWEB)
Wallace, R.J. [Univ. of New Hampshire, Durham, NH (United States)
1996-12-31
Two methods are described for enhancing performance of branch and bound methods for overconstrained CSPs. These methods improve either the upper or lower bound, respectively, during search, so the two can be combined. Upper bounds are improved by using heuristic repair methods before search to find a good solution quickly, whose cost is used as the initial upper bound. The method for improving lower bounds is an extension of directed arc consistency preprocessing, used in conjunction with forward checking. After computing directed arc consistency counts, inferred counts are computed for all values based on minimum counts for values of adjacent variables that are later in the search order. This inference process can be iterated, so that counts are cascaded from the end to the beginning of the search order, to augment the initial counts. Improvements in time and effort are demonstrated for both techniques using random problems.
Brusco, Michael J.; Stahl, Stephanie
2005-01-01
There are two well-known methods for obtaining a guaranteed globally optimal solution to the problem of least-squares unidimensional scaling of a symmetric dissimilarity matrix: (a) dynamic programming, and (b) branch-and-bound. Dynamic programming is generally more efficient than branch-and-bound, but the former is limited to matrices with…
A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem
DEFF Research Database (Denmark)
Jepsen, Mads Kehlet; Spoorendonk, Simon; Røpke, Stefan
2013-01-01
This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow m...... model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality surpassing previous exact algorithms....
Managing Water Quality under Uncertainty: Application of a New Stochastic Branch and Bound Method
Lence, B.J.; Ruszczynski, A.
1996-01-01
The problem of water quality management under uncertain emission levels, reaction rates and pollutant transport is considered. Various performance measures: reliability, resiliency and vulnerability are taken into account. A general methodology for finding a cost-effective water quality management program is developed. The approach employs a new idea of the stochastic branch and bound method, which combines random estimates of the performance for subsets of decisions with iterative refinement...
Parallel Branch-and-Bound Methods for the Job Shop Scheduling
DEFF Research Database (Denmark)
Clausen, Jens; Perregaard, Michael
1998-01-01
-and-bound algorithms for JSS on a 16-processor MEIKO computing surface with Intel i860 processors and perform extensive computational testing using classical publicly available benchmark problems. The parallel part of one of the implementations is based on a similar parallel code for quadratic assignment problems...
Optimal chiller sequencing by branch and bound method for saving energy
International Nuclear Information System (INIS)
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
A branch and bound for single machine stochastic scheduling to minimize the maximum lateness ,
Directory of Open Access Journals (Sweden)
Hamidreza Haddad
2012-04-01
Full Text Available This paper studies the problem of single machine stochastic scheduling with random processing times, deterministic due dates and an independent setup time. The jobs are also deteriorated based on the position, which their processes are done. The objective function is to find a schedule of jobs, which minimizes the expected value of maximum lateness. A branch and bound scheme is presented to solve the problem analytically and a simulated annealing meta-heuristic (SA is also provided for solving the problem in larger scales. Computational experiments demonstrate that the proposed SA is capable of finding near optimal solutions with very low gap.
Directory of Open Access Journals (Sweden)
Mukhacheva E.A.
2000-01-01
Full Text Available Two algorithms for the one-dimensional cutting problem, namely, a modified branch-and-bound method (exact method and a heuristic sequential value correction method are suggested. In order to obtain a reliable assessment of the efficiency of the algorithms, hard instances of the problem were considered and from the computational experiment it seems that the efficiency of the heuristic method appears to be superior to that of the exact one, taking into account the computing time of the latter. A detailed description of the two methods is given along with suggestions for their improvements.
DEFF Research Database (Denmark)
Gadegaard, Sune Lauth; Ehrgott, Matthias; Nielsen, Lars Relund
2016-01-01
strengthened by cutting planes. In addition, we suggest an extension of the branching strategy "Pareto branching''. Extensive computational results obtained for the bi-objective single source capacitated facility location problem prove the effectiveness of the algorithms....... bound sets that prevents us from solving the bi-objective LP-relaxation of each branching node. To strengthen the lower bound sets, we propose a bi-objective cutting plane algorithm that dynamically adjusts the weights of the objective functions such that different parts of the feasible set are...
International Nuclear Information System (INIS)
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)
International Nuclear Information System (INIS)
Highlights: • A hierarchical MILP method for optimal design of energy supply systems is proposed. • Lower bounds for the optimal value of the objective function are evaluated. • Bounding operations using the lower bounds are proposed. • The proposed method is implemented into open and commercial MILP solvers. • Validity and effectiveness of the proposed method are clarified by case studies. - Abstract: To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function to be minimized are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified
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 speci...... specific inequalities. Results also indicate that introducing the cuts leads to a smaller branch and bound tree and faster solution times overall.......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...
International Nuclear Information System (INIS)
Nuclear magnetic resonance (NMR) assignment of small molecules is presented as a typical example of a combinatorial optimization problem in chemical physics. Three strategies that help improve the efficiency of solution search by the branch and bound method are presented: 1. reduction of the size of the solution space by resort to a condensed structure formula, wherein symmetric nuclei are grouped together; 2. partitioning of the solution space based on symmetry, that becomes the basis for an efficient branching procedure; and 3. a criterion of selection of input restrictions that leads to increased gaps between branches and thus faster pruning of non-viable solutions. Although the examples chosen to illustrate this work focus on small-molecule NMR assignment, the results are generic and might help solving other combinatorial optimization problems
International Nuclear Information System (INIS)
Interval Bound Algorithm is a well performance algorithm to optimize reactor reloading pattern problem. In order to improve the performance of the algorithm further, this paper added 'elitism strategy' to it. The numerical result showed that the improved algorithm became better than the basic algorithm in terms of both solution quality and convergence speed. Moreover, in order to solve multi-modal reloading pattern optimization problem, the multi-interval-model was added to the algorithm. The numerical result also illustrated that the re-improved algorithm was able to find multi-modal optimization solutions simultaneously without increasing of calculation load. With the two improvement measures, Interval Bound Algorithm has performed better in realistic application. (authors)
A branch-and-cut algorithm for the capacitated open vehicle routing problem
DEFF Research Database (Denmark)
Letchford, A.N.; Lysgaard, Jens; Eglese, R.W.
2007-01-01
In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch...... assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem....
A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem
DEFF Research Database (Denmark)
Letchford, Adam N.; Lysgaard, Jens; Eglese, Richard W.
In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch...... assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem....
Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
G. Galambos; A. van Vliet (André)
1994-01-01
textabstractIn this paper we discuss lower bounds for the asymptotic worst case ratio of on-line algorithms for different kind of bin packing problems. Recently, Galambos and Frenk gave a simple proof of the 1.536 ... lower bound for the 1-dimensional bin packing problem. Following their ideas, we p
A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands
DEFF Research Database (Denmark)
Christiansen, Christian Holk; Lysgaard, Jens; Wøhlk, Sanne
2009-01-01
We address the Capacitated Arc Routing Problem with Stochastic Demands (CARPSD), which we formulate as a Set Partitioning Problem. The CARPSD is solved by a Branch-and-Price algorithm, which we apply without graph transformation. The demand's stochastic nature is incorporated into the pricing pro...... problem. Computational results are reported....
Persistence-Based Branch Misprediction Bounds for WCET Analysis
DEFF Research Database (Denmark)
Puffitsch, Wolfgang
Branch prediction is an important feature of pipelined processors to achieve high performance. However, it can lead to overly pessimistic worst-case execution time (WCET) bounds when being modeled too conservatively. This paper presents bounds on the number of branch mispredictions for local...... dynamic branch predictors. To handle interferences between branch instructions we use the notion of persistence, a concept that is also found in cache analyses. The bounds apply to branches in general, not only to branches that close a loop. Furthermore, the bounds can be easily integrated into integer...... linear programming formulations of the WCET problem. An evaluation on a number of benchmarks shows that with these bounds, dynamic branch prediction does not necessarily lead to higher WCET bounds than static prediction schemes....
Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep
Daskalakis, Constantinos; Roch, Sebastien
2008-01-01
We introduce a new phylogenetic reconstruction algorithm which, unlike most previous rigorous inference techniques, does not rely on assumptions regarding the branch lengths or the depth of the tree. The algorithm returns a forest which is guaranteed to contain all edges that are: 1) sufficiently long and 2) sufficiently close to the leaves. How much of the true tree is recovered depends on the sequence length provided. The algorithm is distance-based and runs in polynomial time.
JPLEX: Java Simplex Implementation with Branch-and-Bound Search for Automated Test Assembly
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…
Parameterized Expectations Algorithm and the Moving Bounds: a comment on convergence properties
Pérez, Javier J.; A. Jesús Sánchez
2005-01-01
In this paper we analyze the convergence properties of the moving bounds algorithm to initialize the Parameterized Expectations Algorithm suggested by Maliar and Maliar (2003) [Journal of Business and Economic Statistics 1, pp. 88-92]. We carry out a Monte Carlo experiment to check its performance against some initialization alternatives based on homotopy principles. We do so within the framework of two standard neoclassical growth models. We show that: (i) speed of convergence is poor as com...
A hybrid of genetic algorithm and Fletcher-Reeves for bound constrained optimization problems
Asoke Kumar Bhunia; Pintu Pal; Samiran Chattopadhyay
2015-01-01
In this paper a hybrid algorithm for solving bound constrained optimization problems having continuously differentiable objective functions using Fletcher Reeves method and advanced Genetic Algorithm (GA) have been proposed. In this approach, GA with advanced operators has been applied for computing the step length in the feasible direction in each iteration of Fletcher Reeves method. Then this idea has been extended to a set of multi-point approximations instead of single point approximation...
Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
Ling, Shuyang; Strohmer, Thomas
2015-01-01
Consider $r$ sensors, each one intends to send a function $x_i$ (e.g. a signal or image) to a receiver common to all $r$ sensors. Before transmission, each $x_i$ is multiplied by an "encoding matrix" $A_i$. During transmission each $A_ix_i$ gets convolved with a function $h_i$. The receiver records the function $y$, given by the sum of all these convolved signals. Assume that the receiver knowns all the $A_i$, but does neither know the $x_i$ nor the $h_i$. When and under which conditions is i...
Energy Technology Data Exchange (ETDEWEB)
Joseph W. Nielsen; Akira Tokurio; Robert Hiromoto; Jivan Khatry
2014-06-01
Traditional Probabilistic Risk Assessment (PRA) methods have been developed and are quite effective in evaluating risk associated with complex systems, but lack the capability to evaluate complex dynamic systems. These time and energy scales associated with the transient may vary as a function of transition time to a different physical state. Dynamic PRA (DPRA) methods provide a more rigorous analysis of complex dynamic systems, while complete, results in issues associated with combinatorial explosion. In order to address the combinatorial complexity arising from the number of possible state configurations and discretization of transition times, a characteristic scaling metric (LENDIT – length, energy, number, distribution, information and time) is proposed as a means to describe systems uniformly and thus provide means to describe relational constraints expected in the dynamics of a complex (coupled) systems. Thus when LENDIT is used to characterize four sets – ‘state, system, resource and response’ (S2R2) – describing reactor operations (normal and off-normal), LENDIT and S2R2 in combination have the potential to ‘branch and bound’ the state space investigated by DPRA. In this paper we introduce the concept of LENDIT scales and S2R2 sets applied to a branch-and-bound algorithm and apply the methods to a station black out transient (SBO).
A branch-and-price algorithm for the capacitated facility location problem
DEFF Research Database (Denmark)
Klose, Andreas; Görtz, Simon
2007-01-01
The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize...... operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order 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...
Kim, Nam-Geun; Park, Youngsu; Kim, Jong-Wook; Kim, Eunsu; Kim, Sang Woo
In this paper, we present a recently developed pattern search method called Genetic Pattern Search algorithm (GPSA) for the global optimization of cost function subject to simple bounds. GPSA is a combined global optimization method using genetic algorithm (GA) and Digital Pattern Search (DPS) method, which has the digital structure represented by binary strings and guarantees convergence to stationary points from arbitrary starting points. The performance of GPSA is validated through extensive numerical experiments on a number of well known functions and on robot walking application. The optimization results confirm that GPSA is a robust and efficient global optimization method.
International Nuclear Information System (INIS)
The first experimental observation of bound-state beta-decay showed, that due solely to the electron stripping, a stable nuclide, e.g. 163Dy, became unstable. Also a drastic modification of the half-life of bare 187Re, from 4.12(2) x 1010 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. 207Tl 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 207Tl81+ 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 207Pb81+ as a daughter nuclide, or to a continuum state and lead to 207Pb82+, 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 207Tl81+, 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 207Tl. The half-life of this isomeric state was measured as 1.47(32) s, which shows a small deviation compared to the half-life for
International Nuclear Information System (INIS)
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 hybrid of genetic algorithm and Fletcher-Reeves for bound constrained optimization problems
Directory of Open Access Journals (Sweden)
Asoke Kumar Bhunia
2015-04-01
Full Text Available In this paper a hybrid algorithm for solving bound constrained optimization problems having continuously differentiable objective functions using Fletcher Reeves method and advanced Genetic Algorithm (GA have been proposed. In this approach, GA with advanced operators has been applied for computing the step length in the feasible direction in each iteration of Fletcher Reeves method. Then this idea has been extended to a set of multi-point approximations instead of single point approximation to avoid the convergence of the existing method at local optimum and a new method, called population based Fletcher Reeves method, has been proposed to find the global or nearer to global optimum. Finally to study the performance of the proposed method, several multi-dimensional standard test functions having continuous partial derivatives have been solved. The results have been compared with the same of recently developed hybrid algorithm with respect to different comparative factors.
A branch-and-cut algorithm for the capacitated profitable tour problem
DEFF Research Database (Denmark)
Jepsen, Mads Kehlet; Petersen, Bjørn; Spoorendonk, Simon;
2014-01-01
This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated...... with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved...... instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to...
Frecon, Jordan; Didier, Gustavo; Pustelnik, Nelly; Abry, Patrice
2016-08-01
Self-similarity is widely considered the reference framework for modeling the scaling properties of real-world data. However, most theoretical studies and their practical use have remained univariate. Operator Fractional Brownian Motion (OfBm) was recently proposed as a multivariate model for self-similarity. Yet it has remained seldom used in applications because of serious issues that appear in the joint estimation of its numerous parameters. While the univariate fractional Brownian motion requires the estimation of two parameters only, its mere bivariate extension already involves 7 parameters which are very different in nature. The present contribution proposes a method for the full identification of bivariate OfBm (i.e., the joint estimation of all parameters) through an original formulation as a non-linear wavelet regression coupled with a custom-made Branch & Bound numerical scheme. The estimation performance (consistency and asymptotic normality) is mathematically established and numerically assessed by means of Monte Carlo experiments. The impact of the parameters defining OfBm on the estimation performance as well as the associated computational costs are also thoroughly investigated.
AnkurPachauriand Gursaran
2012-01-01
In search based test data generation, the problem of test data generation is reduced to that of function minimization or maximization.Traditionally, for branch testing, the problem of test data generation has been formulated as a minimization problem. In this paper we define an alternate maximization formulation and experimentally compare it with the minimization formulation. We use a genetic algorithm as the search technique and in addition to the usual genetic algorithm opera...
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
, shows some performance difficulty due to large search trees. The second method, which branches on forbidden and forced edge sequences, demonstrates much better performance. The latter also outperforms a leading exact solution method from the literature. Furthermore, a heuristic algorithm is presented....... The heuristic is fast and yields good solution values. (C) 2011 Elsevier B.V. All rights reserved....
DEFF Research Database (Denmark)
Robenek, Tomáš; Umang, Nitish; Bierlaire, Michel;
2014-01-01
In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the...... differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve......-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational...
Refined Error Bounds for Several Learning Algorithms
Hanneke, Steve
2015-01-01
This article studies the achievable guarantees on the error rates of certain learning algorithms, with particular focus on refining logarithmic factors. Many of the results are based on a general technique for obtaining bounds on the error rates of sample-consistent classifiers with monotonic error regions, in the realizable case. We prove bounds of this type expressed in terms of either the VC dimension or the sample compression size. This general technique also enables us to derive several ...
Properties of branching exponential flights in bounded domains
International Nuclear Information System (INIS)
In a series of recent works, important results have been reported concerning the statistical properties of exponential flights evolving in bounded domains, a widely adopted model for finite-speed transport phenomena (Blanco S. and Fournier R., Europhys. Lett., 61 (2003) 168; Mazzolo A., Europhys. Lett., 68 (2004) 350; Benichou O. et al., Europhys. Lett., 70 (2005) 42). Motivated by physical and biological systems where random spatial displacements are coupled with Galton-Watson birth-death mechanisms, such as neutron multiplication, diffusion of reproducing bacteria or spread of epidemics, in this letter we extend those results in two directions, via a Feynman-Kac formalism. First, we characterize the occupation statistics of exponential flights in the presence of absorption and branching, and give explicit moment formulas for the total length travelled by the walker and the number of performed collisions in a given domain. Then, we show that the survival and escape probability can be derived as well by resorting to a similar approach. (authors)
Zhou, YuQian
2012-01-01
This paper proposes a method to find efficient bounded algorithms of NPC problems by machine enumeration. The key contributions are: * On Universal Turing Machines, a program's time complexity should be characterized as: execution time(n) = loading time(n) + running time(n). * Introduces the concept of bounded algorithms; proposes a comparison based criterion to decide if a bounded algorithm is inefficient; and establishes the length upper bound of efficient bounded programs. * Introduces a new way to evaluate program complexity by using the growth rate characteristic function, which is more easily machine checkable based on observations.
Algorithms for Quantum Branching Programs Based on Fingerprinting
Ablayev, Farid; 10.4204/EPTCS.9.1
2009-01-01
In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.
New physics upper bound on the branching ratio of B_s--> l+ l- and B_s--> l+ l- gamma
Alok, A K; Alok, Ashutosh Kumar
2007-01-01
We consider the most general new physics effective Lagrangian for b--> s l+ l-. We derive the upper limit on the branching ratio for the processes B_s--> l^+ l- where l=e, mu, subject to the current experimental bounds on related processes, B--> (K,K*) l+ l-. If the new physics interactions are of vector/axial-vector form, the present measured rates for B--> (K,K*) l+ l- constrain B_s--> l+ l to be of the same order of magnitude as their respective Standard Model (SM) predictions. On the other hand, if the new physics interactions are of scalar/pseudoscalar form, B--> (K,K*) l+ l- rates do not impose any useful constraint on B_s--> l+ l- and the branching ratios of these decays can be as large as present experimental upper bounds. If future experiments measure B_s--> l+ l- to be > 10^{-8} then the new physics giving rise to these decays has to be of the scalar/pseudoscalar form. We also consider the effect of new physics on B_s--> l+ l- gamma subject to the present experimental constraints on B--> (K,K*) l+ l...
R Ball; Lee, J.
1996-01-01
We prove that a new, irreversible growth algorithm, Non-Deletion Reaction-Limited Cluster-cluster Aggregation (NDRLCA), produces equilibrium Branched Polymers, expected to exhibit Lattice Animal statistics [1]. We implement NDRLCA, off-lattice, as a computer simulation for embedding dimension d=2 and 3, obtaining values for critical exponents, fractal dimension D and cluster mass distribution exponent τ: d=2,D≈1.53±0.05,τ= 1.09±0.06; d=3,D=1.96±0.04,τ=1.50±0.04 in good agreement with theoreti...
A fast and simple branching algorithm for solving small scale fixed-charge transportation problem
Krzysztof Kowalski; Benjamin Lev; Wenjing Shen; Yan Tu
2014-01-01
In this paper, we develop a simple algorithm for obtaining the global solution to a small scale fixed-charge transportation problem (FCTP). The procedure itself is very quick. The proposed method solves FCTP by decomposing the problem into series of smaller sub-problems, which is novel and can be useful to researchers solving any size of the problem.
A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands
DEFF Research Database (Denmark)
Christiansen, Christian Holk; Lysgaard, Jens
This article introduces a new exact algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD). The CVRPSD can be formulated as a Set Partitioning Problem and it is shown that the associated column generation subproblem can be solved using a dynamic programming scheme....... Computational experiments show promising results....
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....
Nghia, Nguyen Duc; Binh, Huynh Thi Thanh
2008-01-01
We have introduced the heuristic algorithm for solving BDMST problem, called CBRC. The experiment shows that CBRC have best result than the other known heuristic algorithm for solving BDMST prolem on Euclidean instances. The best solution found by the genetic algorithm which uses best heuristic algorithm or only one heuristic algorithm for initialization the population is not better than the best solution found by the genetic algorithm which uses mixed heuristic algorithms (randomized heurist...
Cramér-Rao Bounds and Estimation Algorithms for Delay/Doppler and Conventional Altimetry
Halimi, Abderrahim; Mailhes, Corinne; Tourneret, J. -Y.
2013-01-01
International audience Delay/Doppler radar altimetry has been receiving an increasing interest, especially since the launch of the first altimeter in 2010. It aims at reducing the measurement noise and increasing the along-track resolution in comparison with conventional pulse limited altimetry. A semi-analytical model was recently introduced for this new generation of delay/Doppler altimeters. The first contribution of this paper is the derivation of the Cramér-Rao bounds (CRBs) associat...
Çağlar, F; Ozbek, I Y
2012-01-01
Heart sound localization in chest sound is an essential part for many heart sound cancellation algorithms. The main difficulty for heart sound localization methods is the precise determination of the onset and offset boundaries of the heart sound segment. This paper presents a novel method to estimate lower and upper bounds for the onset and offset of the heart sound segment, which can be used as anchor points for more precise estimation. For this purpose, first chest sound is divided into frames and then entropy and smoothed entropy features of these frames are extracted, and used in the Convex-hull algorithm to estimate the upper and lower bounds for heart sound boundaries. The Convex-hull algorithm constructs a special type of envelope function for entropy features and if the maximal difference between the envelope function and the entropy is larger than a certain threshold, this point is considered as a heart sound bound. The results of the proposed method are compared with a baseline method which is a modified version of a well-known heart sound localization method. The results show that the proposed method outperforms the baseline method in terms of accuracy and detection error rate. Also, the experimental results show that smoothing entropy features significantly improves the performance of both baseline and proposed methods. PMID:23366867
New physics upper bound on the branching ratio of B_s --> l+ l-
Alok, A K; Alok, Ashutosh Kumar
2005-01-01
We consider new physics interactions for b --> s l+ l- of the form vector/axial-vector. We derive the upper limit on the branching ratio for the processes B_s --> l+ l-, where l=e or mu, subject to the current experimental bounds on related processes, B --> K l+ l- and B --> K* l+ l-. We obtain 3 sigma upper bounds B(B_s --> e+ e-) mu+ mu-) < 5*10^(-9).
A branch-and-price algorithm for the long-term home care scheduling problem
DEFF Research Database (Denmark)
Gamst, Mette; Jensen, Thomas Sejr
2012-01-01
In several countries, home care is provided for certain citizens living at home. The long-term home care scheduling problem is to generate work plans such that a high quality of service is maintained, the work hours of the employees are respected, and the overall cost is kept as low as possible. We...... propose a branchand-price algorithm for the long-term home care scheduling problem. The pricing problem generates a one-day plan for an employee, and the master problem merges the plans with respect to regularity constraints. The method is capable of generating plans with up to 44 visits during one week....
A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application
Gutin, Gregory; Yeo, Anders
2011-01-01
Let $F$ be a CNF formula with $n$ variables and $m$ clauses. $F$ is $t$-satisfiable if for any $t$ clauses in $F$, there is a truth assignment which satisfies all of them. Lieberherr and Specker (1982) and, later, Yannakakis (1994) proved that in each 3-satisfiable CNF formula at least 2/3 of its clauses can be satisfied by a truth assignment. Yannakakis's proof utilizes the fact that 2/3 m$ is a lower bound on the expected number of clauses satisfied by a random truth assignment over a certain distribution. A CNF formula $F$ is called \\emph{expanding} if for every subset $X$ of the variables of $F$, the number of clauses containing variables of $X$ is not smaller than $|X|.$ In this paper we strengthen the 2/3 m bound by showing that, for every expanding 3-satisfiable CNF formula $F$, at least 2/3 m + \\rho n$ clauses of $F$ can be satisfied by a truth assignment, where $\\rho(>0.0019)$ is a constant. Our proof uses the probabilistic method with a sophisticated distribution for truth values. We use the bound 2...
Ait moussa, Abdellah; Jassemnejad, Bahaeddin
2014-05-01
Nanocomposites with high-aspect ratio fillers attract enormous attention because of the superior physical properties of the composite over the parent matrix. Nanocomposites with functionalized graphene as fillers did not produce the high thermal conductivity expected due to the high interfacial thermal resistance between the functional groups and graphene flakes. We report here a robust and efficient technique that identifies the configuration of the functionalities for improved thermal conductivity. The method combines linearization of the interatomic interactions, calculation, and optimization of the thermal conductivity using the globalized and bounded Nelder-Mead algorithm.
International Nuclear Information System (INIS)
, number, distribution, information and time) is proposed as a means to describe systems uniformly and thus provide means to describe relational constraints expected in the dynamics of a complex (coupled) systems. Thus when LENDIT is used to characterize four sets - 'state, system, resource and response' (S2R2) - describing reactor operations (normal and off-normal), LENDIT and S2R2 in combination have the potential to 'branch and bound' the state space investigated by DPRA. LENDIT and S2R2 provide a consisting methodology across both deterministic and heuristic domains. This paper explores the reduction of a PWR's state-space using a RELAP5 model of a plant subject to a SBO. We introduce LENDIT metrics and S2R2 sets to show the branch-and-bound concept. (author)
Directory of Open Access Journals (Sweden)
Hadi Mokhtari
2013-01-01
Full Text Available In this paper, the problem of received order scheduling by a manufacturer, with the measure of maximum completion times of orders, has been formulated and then an analytical approach has been devised for its solution. At the beginning of a planning period, the manufacturer receives a number of orders from customers, each of which requires two different stages for processing. In order to minimize the work in process inventories, the no-wait condition between two operations of each order is regarded. Then, the equality of obtained schedules is proved by machine idle time minimization, as objective, with the schedules obtained by maximum completion time minimization. A concept entitled “Order pairing” has been defined and an algorithm for achieving optimal order pairs which is based on symmetric assignment problem has been presented. Using the established order pairs, an upper bound has been developed based on contribution of every order pair out of total machines idle time. Out of different states of improving upper bound, 12 potential situations of order pairs sequencing have been also evaluated and then the upper bound improvement has been proved in each situation, separately. Finally, a heuristic algorithm has been developed based on attained results of pair improvement and a case study in printing industry has been investigated and analyzed to approve its applicability.
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
Artigues, Christian; Gendreau, Michel; Rousseau, Louis-Martin; Vergnaud, Adrien
2009-01-01
We propose exact hybrid methods based on integer linear programming and constraint programming for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a constraint programming (CP) formulation associated with a linear programming (LP) relaxation. Under a CP framework, the LP-relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two diffe...
Improved branch and bound algorithm for detecting SNP-SNP interactions in breast cancer
Chuang, Li-Yeh; Chang, Hsueh-Wei; Lin, Ming-Cheng; Yang, Cheng-Hong
2013-01-01
Background Single nucleotide polymorphisms (SNPs) in genes derived from distinct pathways are associated with a breast cancer risk. Identifying possible SNP-SNP interactions in genome-wide case–control studies is an important task when investigating genetic factors that influence common complex traits; the effects of SNP-SNP interaction need to be characterized. Furthermore, observations of the complex interplay (interactions) between SNPs for high-dimensional combinations are still computati...
Pebbles and Branching Programs for Tree Evaluation
Cook, Stephen; Wehr, Dustin; Braverman, Mark; Santhanam, Rahul
2010-01-01
We introduce the Tree Evaluation Problem, show that it is in logDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = {1,...,k}, and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its d-ary function applied to the values of its d children. The output is the value of the root. We show that the standard black pebbling algorithm applied to the binary tree of height h yields a deterministic k-way branching program with Theta(k^h) states solving this problem, and we prove that this upper bound is tight for h=2 and h=3. We introduce a simple semantic restriction called "thrifty" on k-way branching programs solving tree evaluation problems and show that the same state bound of Theta(k^h) is tight (up to a constant factor) for all h >= 2 for deterministic thrift...
Institute of Scientific and Technical Information of China (English)
LIU Xiao; WANG Cheng-en
2005-01-01
This paper addresses a single item dynamic lot-sizing model with inventory capacity and out-sourcing. The goal is to minimize the total costs of production, setup, inventory holding and out-sourcing. Two versions of an out-sourcing model with time-varying costs are considered: stock out case and conservation case. Zero Inventory Order property has been found and some new properties are obtained in an optimal solution. Dynamic programming algorithms are developed to solve the problem in strongly polynomial time respectively. Furthermore, some numerical results demonstrate that the approach proposed is efficient and applicable.
Upper and lower bounds for disadvantage factors as a test of algorithm used in a synthesis method
International Nuclear Information System (INIS)
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
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.
New physics upper bound on the branching ratio of B_s--> l+ l- and B_s--> l+ l- gamma
Alok, Ashutosh Kumar; Sankar, S. Uma
2006-01-01
We consider the most general new physics effective Lagrangian for b--> s l+ l-. We derive the upper limit on the branching ratio for the processes B_s--> l^+ l- where l=e, mu, subject to the current experimental bounds on related processes, B--> (K,K*) l+ l-. If the new physics interactions are of vector/axial-vector form, the present measured rates for B--> (K,K*) l+ l- constrain B_s--> l+ l to be of the same order of magnitude as their respective Standard Model (SM) predictions. On the othe...
Better Polynomial Algorithms on Graphs of Bounded Rank-Width
Ganian, Robert; Hliněný, Petr
Although there exist many polynomial algorithms for NP-hard problems running on a bounded clique-width expression of the input graph, there exists only little comparable work on such algorithms for rank-width. We believe that one reason for this is the somewhat obscure and hard-to-grasp nature of rank-decompositions. Nevertheless, strong arguments for using the rank-width parameter have been given by recent formalisms independently developed by Courcelle and Kanté, by the authors, and by Bui-Xuan et al. This article focuses on designing formally clean and understandable "pseudopolynomial" (XP) algorithms solving "hard" problems (non-FPT) on graphs of bounded rank-width. Those include computing the chromatic number and polynomial or testing the Hamiltonicity of a graph and are extendable to many other problems.
New Facets and a Branch-and-Cut Algorithm for the Weighted Clique Problem
DEFF Research Database (Denmark)
Sørensen, Michael Malmros
2001-01-01
We consider a polyhedral approach to the weighted maximal b-clique problem. Given a node- and edge-weighted complete graph the problem is to find a complete subgraph (clique) with no more than b nodes such that the sum of the weights of all nodes and edges in the clique is maximal. We introduce...... 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 of...
New facets and a branch-and-cut algorithm for the weighted clique problem
DEFF Research Database (Denmark)
Sørensen, Michael Malmros
2004-01-01
We consider a polyhedral approach to the weighted maximal b-clique problem. Given a node- and edge-weighted complete graph the problem is to find a complete subgraph (clique) with no more than b nodes such that the sum of the weights of all nodes and edges in the clique is maximal. We introduce...... 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...
Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem
DEFF Research Database (Denmark)
Bektas, Tolga; Erdogan, Günes; Røpke, Stefan
2011-01-01
The Generalized Vehicle Routing Problem (GVRP) consists of nding a set of routes for a number of vehicles with limited capacities on a graph with the vertices partitioned into clusters with given demands such that the total cost of travel is minimized and all demands are met. This paper offers four...
A Branch and Cut algorithm for the container shipping network design problem
Reinhardt, Line Blander; Kallehauge, Brian; Pisinger, David
2010-01-01
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 ...
A Branch and Cut algorithm for the container shipping network design problem
DEFF Research Database (Denmark)
Reinhardt, Line Blander; Pisinger, David
2012-01-01
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...
A General Nonlinear Optimization Algorithm for Lower Bound Limit Analysis
DEFF Research Database (Denmark)
Krabbenhøft, Kristian; Damkilde, Lars
2003-01-01
finite element discretization or yield criterion is required. As with interior point methods for linear programming the number of iterations is affected only little by the problem size. Some practical implementation issues are discussed with reference to the special structure of the common lower bound......The non-linear programming problem associated with the discrete lower bound limit analysis problem is treated by means of an algorithm where the need to linearize the yield criteria is avoided. The algorithm is an interior point method and is completely general in the sense that no particular...... load optimization problem, and finally the efficiency and accuracy of the method is demonstrated by means of examples of plate and slab structures obeying different non-linear yield criteria....
Branch-and-cut-and-price for the traveling salesman problem with time windows
DEFF Research Database (Denmark)
Røpke, Stefan; Madsen, Oli B.G.
paradigms such as branch-and-cut, dynamic programming and constraint programming. We cannot conclude that the branch-and-cut-and-price approach always is superior to the others paradigms, but several instances are reported solved to optimality for the rst time and bounds are strengthened for other, still...... generation process converges slowly for the problem and therefore a stabilization procedure is implemented. Valid inequalities expressed in the original, arc-based variables are added to the LP relaxation to strengthen the lower bound. The proposed algorithm is compared to exact algorithms based on other...
Kohei Arai
2012-01-01
Method for visualization of URL link structure and URL retrievals using internal structure of URLs based on brunch and bound method is proposed. Twisting link structure of URLs can be solved by the proposed visualization method. Also some improvements are observed for the proposed brunch and bound based method in comparison to the conventional URL retrieval methods.
Friel, Thilo-Thomas; Harrison, R.
1998-01-01
Three novel algorithms are presented; the linear programming (LP) machine for pattern classification, the LP machine for regression estimation and the set-reduction (SR) algorithm. The LP machine is a learning machine which achieves solutions as good as the SV machine by only maximising a linear cost-function (SV machine are based on quadratic programming). The set-reduction algorithm improves the speed and accuracy of LP machines, SV machines and other related algorithms. An LP machines's de...
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem
DEFF Research Database (Denmark)
Fukasawa, R.; Longo, H.; Lysgaard, Jens; Poggi de Aragão, M.; Reis, M.; Uchoa, E.; Werneck, R.F.
2006-01-01
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......The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a...
R. Freling (Richard); R.M. Lentink (Ramon); A.P.M. Wagelmans (Albert)
2001-01-01
textabstractThis paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. We briefly discuss the mathematical background of the solver, of which most part is covered
Improved Bounds on Quantum Learning Algorithms
Atici, A; Atici, Alp; Servedio, Rocco A.
2004-01-01
In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples. Hunziker et al. conjectured that for any class C of Boolean functions, the number of quantum black-box queries which are required to exactly identify an unknown function from C is at most $O(\\frac{\\log |C|}{\\sqrt{{\\hat{\\gamma}}^{C}}})$, where $\\hat{\\gamma}^{C}$ is a combinatorial parameter of the class C. We essentially resolve this conjecture in the affirmative by giving a quantum algorithm that, for any class C, identifies any unknown function from C using at most $O(\\frac{\\log |C| \\log \\log |C|}{\\sqrt{{\\hat{\\gamma}}^{C}}})$ quantum black-box queries. We consider a range of natural problems intermediate between the exact learning problem (in which the learner must obtain all bits of information about the black-box function) and the usual problem of computing a predicate (in which the learner must obtain only one bit of information about the black-box function). ...
New physics upper bound on the branching ratio of B_s --> l+ l-
Alok, Ashutosh Kumar; Sankar, S. Uma
2005-01-01
We consider the most general new physics effective Lagrangian for b --> s l+ l-. We derive the upper limit on the branching ratio for the processes B_s --> l+ l- where l=e, mu, subject to the current experimental bounds on related processes, B --> K l+ l- and B --> K* l+ l-. If the new physics interactions are of vector/axial-vector form, the present measured rates for B --> (K,K*) l+ l- constrain B(B_s --> l+ l-) to be of the same order of magnitude as their respective Standard Model predict...
Freling, Richard; Lentink, Ramon; Wagelmans, Albert
2001-01-01
textabstractThis paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. We briefly discuss the mathematical background of the solver, of which most part is covered in the Operations Research literature. Crew scheduling is crew planning for one or a few days that results in crew duties or pairings, and crew rostering is crew planning for at least one week for ...
Directory of Open Access Journals (Sweden)
Dinesh Gupta
2012-03-01
Full Text Available Various sheduling algorithm are available forthe operating system to improve CPU utilization.Different scheduling algorithms have differentproperties that work on different schedulingcriterias and the choice of a particular algorithmmay favor one class of processes over another.SJF gives minimum average waiting time for agiven set of processes. The Round Robinalgorithm decreases the response time. In thispaper we have proposed an algorithm which hasresponse time aproximately zero and itincreases the efficiency of I/O boundedprocess.
Analysis of the contact graph routing algorithm: Bounding interplanetary paths
Birrane, Edward; Burleigh, Scott; Kasch, Niels
2012-06-01
Interplanetary communication networks comprise orbiters, deep-space relays, and stations on planetary surfaces. These networks must overcome node mobility, constrained resources, and significant propagation delays. Opportunities for wireless contact rely on calculating transmit and receive opportunities, but the Euclidean-distance diameter of these networks (measured in light-seconds and light-minutes) precludes node discovery and contact negotiation. Propagation delay may be larger than the line-of-sight contact between nodes. For example, Mars and Earth orbiters may be separated by up to 20.8 min of signal propagation time. Such spacecraft may never share line-of-sight, but may uni-directionally communicate if one orbiter knows the other's future position. The Contact Graph Routing (CGR) approach is a family of algorithms presented to solve the messaging problem of interplanetary communications. These algorithms exploit networks where nodes exhibit deterministic mobility. For CGR, mobility and bandwidth information is pre-configured throughout the network allowing nodes to construct transmit opportunities. Once constructed, routing algorithms operate on this contact graph to build an efficient path through the network. The interpretation of the contact graph, and the construction of a bounded approximate path, is critically important for adoption in operational systems. Brute force approaches, while effective in small networks, are computationally expensive and will not scale. Methods of inferring cycles or other librations within the graph are difficult to detect and will guide the practical implementation of any routing algorithm. This paper presents a mathematical analysis of a multi-destination contact graph algorithm (MD-CGR), demonstrates that it is NP-complete, and proposes realistic constraints that make the problem solvable in polynomial time, as is the case with the originally proposed CGR algorithm. An analysis of path construction to complement hop
Lipschitz bounds for noise robustness in compressive sensing: two algorithms
Nicodème, Marc; Dossal, Charles; Turcu, Flavius; Berthoumieu, Yannick
2014-01-01
The paper deals with estimating the local noise robustness in a compressive sensing framework. We provide two algorithms which estimate, for each vector x that can be recovered by $\\ell^1$ minimization, the Lipschitz bounds relating the $\\ell^1$-reconstruction error to the measurement error (or noise) for a given sensing matrix. Classical theoretical estimations, such as those based on the restricted isometry property, theoretically give error bounds estimates depending on RIP constants. Unfo...
Koenigs function and branching processes
Tchikilev, O. G.
2001-01-01
An explicit solution of time-homogeneous pure birth branching processes is described. It gives alternative extensions for the negative binomial distribution (branching processes with immigration) and for the Furry-Yule distribution (branching processes without immigration).
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
Branch-pipe-routing approach for ships using improved genetic algorithm
Sui, Haiteng; Niu, Wentie
2016-05-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.
Bound states and the Bekenstein bound
Bousso, R
2004-01-01
We explore the validity of the generalized Bekenstein bound, S <= pi M a. We define the entropy S as the logarithm of the number of states which have energy eigenvalue below M and are localized to a flat space region of width a. If boundary conditions that localize field modes are imposed by fiat, then the bound encounters well-known difficulties with negative Casimir energy and large species number, as well as novel problems arising only in the generalized form. In realistic systems, however, finite-size effects contribute additional energy. We study two different models for estimating such contributions. Our analysis suggests that the bound is both valid and nontrivial if interactions are properly included, so that the entropy S counts the bound states of interacting fields.
Penentuan Batas Bawah pada Metode Branch and Price
Meliana
2013-01-01
Integer Programming is a specific linear programming where the variables of decision are integer. There are so many kind of way to finish this integer programming; one of them is Branch and Price method. Like Branch and Bound method, in the step to finish the integer programming in Branch and Price method need the iterations that are too long. To make the iteration to be short then should be given the lower bound.
A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms
Sudholt, Dirk
2011-01-01
We present a new method for proving lower bounds on the expected running time of evolutionary algorithms. It is based on fitness-level partitions and an additional condition on transition probabilities between fitness levels. The method is versatile, intuitive, elegant, and very powerful. It yields exact or near-exact lower bounds for LO, OneMax, long k-paths, and all functions with a unique optimum. Most lower bounds are very general: they hold for all evolutionary algorithms that only use b...
An exact approach for single machine scheduling with quadratic earliness and tardiness penalties
Jorge M. S. Valente
2007-01-01
In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose two different lower bounds, as well as a lower bounding procedure that combines these two bounds. Optimal branch-and-bound algorithms are then presented. These algorithms incorporate the proposed lower bound, as well as an insertion-based dominance test. The lower bounding procedure and the branch-and-bound algorithms are tested on a wide set of r...
A BOUND ON THE LIGHT EMITTED DURING THE THERMALLY PULSING ASYMPTOTIC GIANT BRANCH PHASE
International Nuclear Information System (INIS)
The integrated luminosity of the thermally pulsing asymptotic giant branch (TP-AGB) phase is a major uncertainty in stellar population synthesis models. We revise the white dwarf initial-final mass relation (IFMR), incorporating the latest composition and distance measurements for several clusters. Using this IFMR and stellar interiors models, we demonstrate that a significant fraction of the core mass growth for intermediate (1.5 sun sun and 3.5 Msun. Using a simple fuel consumption argument we couple this core mass increase to a lower limit on the TP-AGB phase energy output. We demonstrate that the current TP-AGB models of Pietrinferni et al. and Bertelli et al. systematically grow the core less than we require while the latter predict sufficient integrated light. Our calculated lower bound, coupled with chemical evolution constraints, may provide an upper limit to the integrated luminosity of stars in the TP-AGB phase. Alternatively, a robust measurement of the emitted light in this phase and our constraints could set strong constraints on helium enrichment from TP-AGB stars. We estimate the yields predicted by current models as a function of initial mass. Implications for stellar population studies and prospects for improvements are discussed.
Directory of Open Access Journals (Sweden)
Daniel Morillo-Torres
2015-01-01
Full Text Available En este artículo se aborda el problema de Programación de Tareas con Recursos Restringidos (RCPSP. Para su solución, se desarrolla y se implementa una metodología híbrida que usa como base un algoritmo de Ramificación y Acotamiento con potentes reglas de dominancia, y se combina con cuatro heurísticas determinísticas cuyo objetivo es truncar ramas del árbol de búsqueda, pero, a su vez, minimizar la probabilidad de descartar ramales que contengan soluciones óptimas. En esencia, estas estrategias permiten la repartición de iteraciones en forma mayoritaria y organizada en las regiones más promisorias usando, únicamente, subconjuntos que tengan características similares o iguales a las de las soluciones óptimas en cada nivel del árbol, garantizando así una amplia exploración dentro de la región factible y al mismo tiempo una buena explotación. Finalmente se analiza el desempeño del algoritmo desarrollado mediante la solución de algunos problemas de la librería de prueba PSPLIB.
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...
Improved space bounds for strongly competitive randomized paging algorithms
Moruz, Gabriel; Negoescu, Andrei Laurian (Dipl.-Inf.)
2013-01-01
Paging is one of the prominent problems in the field of on-line algorithms. While in the deterministic setting there exist simple and efficient strongly competitive algorithms, in the randomized setting a tradeoff between competitiveness and memory is still not settled. Bein et al. [4] conjectured that there exist strongly competitive randomized paging algorithms, using o(k) bookmarks, i.e. pages not in cache that the algorithm keeps track of. Also in [4] the first algorithm using O(k) bookma...
Quiver Varieties and Branching
Directory of Open Access Journals (Sweden)
Hiraku Nakajima
2009-01-01
Full Text Available Braverman and Finkelberg recently proposed the geometric Satake correspondence for the affine Kac-Moody group Gaff [Braverman A., Finkelberg M., arXiv:0711.2083]. They conjecture that intersection cohomology sheaves on the Uhlenbeck compactification of the framed moduli space of Gcpt-instantons on $R^4/Z_r$ correspond to weight spaces of representations of the Langlands dual group $G_{aff}^{vee}$ at level $r$. When $G = SL(l$, the Uhlenbeck compactification is the quiver variety of type $sl(r_{aff}$, and their conjecture follows from the author's earlier result and I. Frenkel's level-rank duality. They further introduce a convolution diagram which conjecturally gives the tensor product multiplicity [Braverman A., Finkelberg M., Private communication, 2008]. In this paper, we develop the theory for the branching in quiver varieties and check this conjecture for $G = SL(l$.
New hybrid evolutionary algorithm for solving the bounded diameter minimum spanning tree problem
Directory of Open Access Journals (Sweden)
Sakshi Arora
2009-12-01
Full Text Available Given a connected, weighted, undirected graph G and a bound D, the bounded diameterminimum spanning tree (BDMST problem seeks a spanning tree on G of minimum weight among the treesin which no path between two vertices contains more than D edges. This problem is NP-hard for 4 D |v| -1. In present paper a new randomized greedy heuristic algorithm for solving BDMST is proposed. Anevolutionary algorithm encodes spanning trees as lists of their edges, augmented with their center vertices.It applies operators that maintain the diameter bound and always generate valid offspring trees. Theseoperators are efficient, so the algorithm scales well to larger problem instances. On 25 Euclidean instancesof up to 1000 vertices, the EA improved substantially on solutions found by the randomized greedyheuristic.
Methods and Technologies Branch (MTB)
The Methods and Technologies Branch focuses on methods to address epidemiologic data collection, study design and analysis, and to modify technological approaches to better understand cancer susceptibility.
Rational hybrid Monte Carlo algorithm for theories with unknown spectral bounds
International Nuclear Information System (INIS)
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
An Individual Tree Detection Algorithm for Dense Deciduous Forests with Spreading Branches
Shao, G.
2015-12-01
Individual tree information derived from LiDAR may have the potential to assist forest inventory and improve the assessment of forest structure and composition for sustainable forest management. The algorithms developed for individual tree detection are commonly focusing on finding tree tops to allocation the tree positions. However, the spreading branches (cylinder crowns) in deciduous forests cause such kind of algorithms work less effectively on dense canopy. This research applies a machine learning algorithm, mean shift, to position individual trees based on the density of LiDAR point could instead of detecting tree tops. The study site locates in a dense oak forest in Indiana, US. The selection of mean shift kernels is discussed. The constant and dynamic bandwidths of mean shit algorithms are applied and compared.
Joint MAP bias estimation and data association: algorithms
Danford, Scott; Kragel, Bret; Poore, Aubrey
2007-09-01
The problem of joint maximum a posteriori (MAP) bias estimation and data association belongs to a class of nonconvex mixed integer nonlinear programming problems. These problems are difficult to solve due to both the combinatorial nature of the problem and the nonconvexity of the objective function or constraints. A specific problem that has received some attention in the tracking literature is that of the target object map problem in which one tries match a set of tracks as observed by two different sensors in the presence of biases, which are modeled here as a translation between the track states. The general framework also applies to problems in which the costs are general nonlinear functions of the biases. The goal of this paper is to present a class of algorithms based on the branch and bound framework and the "all-pairs" and k-best heuristics that provide a good initial upper bound for a branch and bound algorithm. These heuristics can be used as part of a real-time algorithm or as part of an "anytime algorithm" within the branch and bound framework. In addition, we consider both the A*-search and depth-first search procedures as well as several efficiency improvements such as gating. While this paper focuses on the algorithms, a second paper will focus on simulations.
Appell, Jürgen; Merentes Díaz, Nelson José
2013-01-01
This monographis a self-contained exposition of the definition and properties of functionsof bounded variation and their various generalizations; the analytical properties of nonlinear composition operators in spaces of such functions; applications to Fourier analysis, nonlinear integral equations, and boundary value problems. The book is written for non-specialists. Every chapter closes with a list of exercises and open problems.
Path-valued branching processes and nonlocal branching superprocesses
Li, Zenghu
2012-01-01
A family of continuous-state branching processes with immigration are constructed as the solution flow of a stochastic equation system driven by time-space noises. The family can be regarded as an inhomogeneous increasing path-valued branching process with immigration. Two nonlocal branching immigration superprocesses can be defined from the flow. We identify explicitly the branching and immigration mechanisms of those processes. The results provide new perspectives into the tree-valued Markov processes of Aldous and Pitman [Ann. Inst. H. Poincare Probab. Statist. 34 (1998), 637--686] and Abraham and Delmas [Ann. Probab. To appear].
Metastability of Bose and Fermi gases on the upper branch
LeClair, Andre; Roditi, Itzhak; Squires, Joshua
2016-01-01
We study three dimensional Bose and Fermi gases in the upper branch, a phase defined by the absence of bound states in the repulsive interaction regime, within an approximation that considers only two-body interactions. Employing a formalism based on the S-matrix, we derive a useful analytic expression that holds on the upper branch in the weak coupling limit. We determine upper branch phase diagrams for both bosons and fermions with techniques valid for arbitrary positive scattering length.
Two-swarm cooperative artificial fish algorithm for bound constrained global optimization
Ana Maria A C Rocha; Costa, M. Fernanda P.; Fernandes, Edite Manuela da G. P.
2014-01-01
This study presents a new two-swarm cooperative ﬁsh intelligence algorithm for solving the bound constrained global optimization problem. The master population is moved by a Lévy distribution and cooperates with the training population that follows mainly the classical ﬁsh behaviors. Some numerical experiments are reported.
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...
Institute of Scientific and Technical Information of China (English)
Chunxia Jia; Detong Zhu
2008-01-01
In this paper we propose an affine scaling interior algorithm via conjugate gradient path for solving nonlinear equality systems subject to bounds on variables.By employing the affine scaling conjugate gradient path search strategy,we obtain an iterative direction by solving the linearize model.By using the line search technique,we will find an acceptable trial step length along this direction which is strictly feasible and makes the objective function nonmonotonically decreasing.The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions.Furthermore,the numerical results of the proposed algorithm indicate to be effective.
Numerical Algorithm for a Class of Linear Fractional Programming Problem
Hongwei Jiao; Kun Li; Jianping Wang
2013-01-01
In this study, a branch and bound algorithm is presented for globally solving a class of linear fractional programming problems. In the algorithm, a linear relaxation method is introduced to generate the linear relaxation programming problem of the investigated linear fractional programming problems. In this study, we pay more attention to the numerical experiments. Several test problems are used to verify the feasibility and computational efficiency of the proposed branch and bound algorithm.
Analysis of imbalanced weather data based on branch-and-bound approach%基于分支限界的不平衡气象数据晴雨分析
Institute of Scientific and Technical Information of China (English)
王剑辉; 梁路; 王彪
2016-01-01
This paper proposed the modified cost-sensitive learning methods to preprocess the imbalance weather data.Con-sidering about the specialty of weather data,it made the value of rainfall per unit time as the cost value.So the data could be divided into two types of rain and non-rain effectively and reasonably.And then it used logic-based approach to analysie the data processed,used branch-and-bound approach to derive a Boolean classifier.Experimental results show that this method is feasible and effective.What’s more,it’s valid to perform any further logic calculation or logic operation on the result of the Boolean classifiers,achieving more flexibility.%提出基于修改的代价敏感学习的方法对不平衡的天气数据进行预处理，结合天气数据自身的特点，以单位时间的降雨量为成本的值，将数据合理有效地区分为下雨和非下雨两类；进而运用基于逻辑的方法对处理完的数据进行分析，运用分支限界算法得出布尔分类器。实验结果表明此方法可行有效，该方法可进一步对布尔分类器结果进行逻辑运算，从而达到更加灵活的操作分类器的效果。
On Entropy Bounds and Holography
Halyo, Edi
2009-01-01
We show that the holographic entropy bound for gravitational systems and the Bekenstein entropy bound for nongravitational systems are holographically related. Using the AdS/CFT correspondence, we find that the Bekenstein bound on the boundary is obtained from the holographic bound in the bulk by minimizing the boundary energy with respect the AdS radius or the cosmological constant. This relation may also ameliorate some problems associated with the Bekenstein bound.
Directory of Open Access Journals (Sweden)
Lin Chen
2014-01-01
Full Text Available To reduce time for collision detection among articulated models, the collision detection algorithm of Hybrid Bounding Volume Hierarchy Tree (HBVHT was proposed to accelerate the speed of culling away triangles. The HBVHT was composed of two phases: A broad phase and a narrow phase. The broad phase consisted of Axis-Aligned Bounding Box (AABB and the Bounding Volume (BV was used to build a Multi-Level Hierarchy Tree (MLHT; the narrow phase was made up of the Oriented Bounding Box (OBB hierarchy trees and triangles. Furthermore, according to the characteristic of hierarchical structure of the HBVHT, an improved cost function was given to analyze the performance of the HBVHT. Experiments were performed between two 6-DOF robots under the Open GL environment. Two robots with the same number of triangles moved with the same trajectory for the collision experiments. Experimental results show that the efficiency of HBVHT algorithm is higher than that of the RAPID and the other two HBVHTs with different structure. The results indicate that the HBVHT algorithm can effectively improve the efficiency of collision detection among the articulated model robots.
Lan, Fujun; Bayraksan, Güzin; Lansey, Kevin
2016-03-01
A regional water supply system design problem that determines pipe and pump design parameters and water flows over a multi-year planning horizon is considered. A non-convex nonlinear model is formulated and solved by a branch-and-reduce global optimization approach. The lower bounding problem is constructed via a three-pronged effort that involves transforming the space of certain decision variables, polyhedral outer approximations, and the Reformulation Linearization Technique (RLT). Range reduction techniques are employed systematically to speed up convergence. Computational results demonstrate the efficiency of the proposed algorithm; in particular, the critical role range reduction techniques could play in RLT based branch-and-bound methods. Results also indicate using reclaimed water not only saves freshwater sources but is also a cost-effective non-potable water source in arid regions. Supplemental data for this article can be accessed at http://dx.doi.org/10.1080/0305215X.2015.1016508.
An Improved Lower Bound Limit State Optimisation Algorithm
DEFF Research Database (Denmark)
Frier, Christian; Damkilde, Lars
2010-01-01
Limit State analysis has been used in engineering practice for many years e.g. the yield-line method for concrete slabs and slip-line solutions in geotechnics. In the recent years there has been an increased interest in numerical Limit State analysis, and today algorithms take into account the non...
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......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 are...... added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the PDPTW are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm....
Branch points of substitutions and closing ordered Bratteli diagrams
Yassawi, Reem
2011-01-01
We study stationary ordered Bratteli diagrams and give necessary and sufficient conditions for these orders to generate a continuous Vershik map. We apply this to finding adic representations for one sided substitution subshifts. We give an algorithm to find the branch points of a substitution, which have to be mapped to the minimal elements of such an ordering. We find adic representations for substitutions with one branch point, and also substitutions all of whose branch points are fixed.
International Nuclear Information System (INIS)
The presence of weakly bound rotationally excited initial states of HD2+ lying just below the lowest dissociation limit has been observed as well as quasi-bound, predissociative final states above the dissociation limit resulting from one-photon excitation of those weakly bound states. The excitation of the initial weakly bound and possibly only few quasi-bound states took place with 1064 nm laser radiation. The possibility of one-photon excitation of the vibrationally excited initial HD2+ ions is considered. The centre-of-mass kinetic energy distributions of the D+ and H+ fragment were used to identify the possible initial and final states involved in the transitions leading to these fragments. The fragment ratio D+/H+ is shown to be critically dependent on the ion source pressure. A strong preference is observed for the D++HD dissociation channel over the H++D2 channel at high source gas pressures. The centre-of-mass energy of the resulting H+ and D+ fragments was found to agree with predicted theoretical values, and suggest that among initially excited HD2+ ions, only a few of these lie initially above the lowest dissociation limit. (author)
Energy Technology Data Exchange (ETDEWEB)
Yousif, F.B. [Centro de Ciencias Fisicas, UNAM, Cuernavaca, Morelos (Mexico)]. E-mail: fbyousif@fis.unam.mx; Cisneros, C.; Urquijo, J. de; Alvarez, I. [Centro de Ciencias Fisicas, UNAM, Cuernavaca, Morelos (Mexico)
2001-03-14
The presence of weakly bound rotationally excited initial states of HD{sub 2}{sup +} lying just below the lowest dissociation limit has been observed as well as quasi-bound, predissociative final states above the dissociation limit resulting from one-photon excitation of those weakly bound states. The excitation of the initial weakly bound and possibly only few quasi-bound states took place with 1064 nm laser radiation. The possibility of one-photon excitation of the vibrationally excited initial HD{sub 2}{sup +} ions is considered. The centre-of-mass kinetic energy distributions of the D{sup +} and H{sup +} fragment were used to identify the possible initial and final states involved in the transitions leading to these fragments. The fragment ratio D{sup +}/H{sup +} is shown to be critically dependent on the ion source pressure. A strong preference is observed for the D{sup +}+HD dissociation channel over the H{sup +}+D{sub 2} channel at high source gas pressures. The centre-of-mass energy of the resulting H{sup +} and D{sup +} fragments was found to agree with predicted theoretical values, and suggest that among initially excited HD{sub 2}{sup +} ions, only a few of these lie initially above the lowest dissociation limit. (author)
Pebbles and Branching Programs for Tree Evaluation
Cook, Stephen; McKenzie, Pierre; Wehr, Dustin; Braverman, Mark; Santhanam, Rahul
2010-01-01
We introduce the Tree Evaluation Problem, show that it is in logDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = {1,...,k}, and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its d-ary function applied to the values of its d childre...
A general non-linear optimization algorithm for lower bound limit analysis
DEFF Research Database (Denmark)
Krabbenhøft, Kristian; Damkilde, Lars
2003-01-01
The non-linear programming problem associated with the discrete lower bound limit analysis problem is treated by means of an algorithm where the need to linearize the yield criteria is avoided. The algorithm is an interior point method and is completely general in the sense that no particular...... load optimization problem. and finally the efficiency and accuracy of the method is demonstrated by means of examples of plate and slab structures obeying different non-linear yield criteria. Copyright (C) 2002 John Wiley Sons. Ltd....... finite element discretization or yield criterion is required. As with interior point methods for linear programming the number of iterations is affected only little by the problem size. Some practical implementation issues are discussed with reference to the special structure of the common lower bound...
EXACT ALGORITHM FOR BIN COVERING
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
This paper presents a new arc flow model for the one-dimensional bin covering problem and an algorithm to solve the problem exactly through a branch-and-bound procedure and the technique of column generation. The subproblems occuring in the procedure of branch-and-bound have the same structure and therefore can be solved by the same algorithm. In order to solve effectively the subproblems which are generally large scale, a column generation algorithm is employed. Many rules found in this paper can improve the performance of the methods.
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...
Conjugacy Growth and Conjugacy Width of Certain Branch Groups
Fink, Elisabeth
2014-01-01
The conjugacy growth function counts the number of distinct conjugacy classes in a ball of radius $n$. We give a lower bound for the conjugacy growth of certain branch groups, among them the Grigorchuk group. This bound is a function of intermediate growth. We further proof that certain branch groups have the property that every element can be expressed as a product of uniformly boundedly many conjugates of the generators. We call this property bounded conjugacy width. We also show how bounde...
Branching processes and neutral evolution
Taïb, Ziad
1992-01-01
The Galton-Watson branching process has its roots in the problem of extinction of family names which was given a precise formulation by F. Galton as problem 4001 in the Educational Times (17, 1873). In 1875, an attempt to solve this problem was made by H. W. Watson but as it turned out, his conclusion was incorrect. Half a century later, R. A. Fisher made use of the Galton-Watson process to determine the extinction probability of the progeny of a mutant gene. However, it was J. B. S. Haldane who finally gave the first sketch of the correct conclusion. J. B. S. Haldane also predicted that mathematical genetics might some day develop into a "respectable branch of applied mathematics" (quoted in M. Kimura & T. Ohta, Theoretical Aspects of Population Genetics. Princeton, 1971). Since the time of Fisher and Haldane, the two fields of branching processes and mathematical genetics have attained a high degree of sophistication but in different directions. This monograph is a first attempt to apply the current sta...
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...
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.
International Nuclear Information System (INIS)
We describe the new developments in version 4 of the public computer code HiggsBounds. Higgs-Bounds 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 ofHiggsBounds are described. The new features are demonstrated by additional example programs. (orig.)
Workshop on Branching Processes and Their Applications
Gonzalez Velasco, Miguel; Martinez, Rodrigo; Molina, Manuel
2010-01-01
Contains papers presented at the Workshop on Branching Processes and Their Applications (WBPA09), held in Badajoz, Spain, April 20-23, 2009, which deal with theoretical and practical aspects of branching process theory
A Super-Polynomial Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it
Friedmann, Oliver
2009-01-01
This paper presents a new lower bound for the discrete strategy improvement algorithm for solving parity games due to Voege and Jurdziski. First, we informally show which structures are difficult to solve for the algorithm. Second, we outline a family of games of quadratic size on which the algorithm requires exponentially many strategy iterations, answering in the negative the long-standing question whether this algorithm runs in polynomial time. Additionally we note that the same family of games can be used to prove a similar result w.r.t. the strategy improvement variant by Schewe.
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.
Weekly Fleet Assignment Model and Algorithm
Institute of Scientific and Technical Information of China (English)
ZHU Xing-hui; ZHU Jin-fu; GONG Zai-wu
2007-01-01
A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity,and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a realworld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was $1591276 one week and the running time was no more than 4 min, which shows that the model and algorithm are fairly good for domestic airline.
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...
Regret Bounds for Deterministic Gaussian Process Bandits
De Freitas, Nando; Smola, Alex; Zoghi, Masrour
2012-01-01
This paper analyses the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al., 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, (Srinivas et al., 2010) proved that the regret vanishes at the approximate rate of $O(\\frac{1}{\\sqrt{t}})$, where t is the number of observations. To complement their result, we attack the deterministic c...
New physics upper bound on the branching ratio of B_s --> l+ l- gamma
Alok, A K; Alok, Ashutosh Kumar
2006-01-01
We consider the effect of new physics on the branching ratio of B_s --> l+ l- gamma where l = e, mu. If the new physics is of the form scalar/pseudoscalar, then it makes no contribution to B_s --> l+ l- gamma, unlike in the case of B_s --> l+ l-, where it can potentially make a very large contribution. New Physics in the form of vector/axial-vector operators cannot lead to large enhancement of B_s --> l+ l- gamma much beyond the Standard Model expectation. But new physics in the form of tensor/pseudo-tensor operators can.
New physics upper bound on the branching ratio of B_s --> l+ l- gamma
Alok, Ashutosh Kumar; Sankar, S. Uma
2006-01-01
We consider the effect of new physics on the branching ratio of B_s--> l+ l- gamma where l=e,mu. If the new physics is of the form scalar/pseudoscalar, then it makes no contribution to B_s--> l+ l- gamma, unlike in the case of B_s--> l+ l-, where it can potentially make a very large contribution. If the new physics is in the form of vector/axial-vector operators, then present data on B-->(K,K^*)l+ l-, does not allow a large enhancement for B_s--> l+ l- gamma. If the new physics is in the form...
A Note on Multitype Branching Process with Bounded Immigration in Random Environment
Institute of Scientific and Technical Information of China (English)
Hua Ming WANG
2013-01-01
In this paper,we study the total number of progeny,W,before regenerating of multitype branching process with immigration in random environment.We show that the tail probability of |W| is of order t-κ as t → ∞,with κ some constant.As an application,we prove a stable law for (L-1) random walk in random environment,generalizing the stable law for the nearest random walk in random environment (see "Kesten,Kozlov,Spitzer:A limit law for random walk in a random environment.Compositio Math.,30,145-168 (1975)").
Electron propagator calculations on linear and branched carbon cluster dianions
Energy Technology Data Exchange (ETDEWEB)
Zakrzewski, V.G.; Ortiz, J.V. [Univ. of New Mexico, Albuquerque, NM (United States)
1994-12-31
Electron propagator calculations have been performed on linear carbon cluster dianions from C{sub 7}{sup 2-} to C{sub 10}{sup 2-} and on branched C{sub 7}{sup 2-}, C{sub 9}{sup 2-} and C{sub 11}{sup 2-} structures which have a central, tricoordinate carbon bound to three branches with alternating long and short bonds. The more stable, branched isomer of C{sub 7}{sup 2-} has a positive vertical ionization energy, but the linear form does not. While linear C{sub 10}{sup 2-} is stable with respect to electron loss, it is not possible to decide from these calculations whether linear C{sub 8}{sup 2-} and C{sub 9}{sup 2-} have the same property. There is evidence that better calculations would obtain bound C{sub 8}{sup 2-} and C{sub 9}{sup 2-} species. All branched dianions have positive, vertical ionization energies. Feynman-Dyson amplitudes for dianion ionization energies display delocalized {pi} bonding, with the two terminal carbons of the longest branches making the largest contributions.
Stochastic Transition between Turbulent Branch and Thermodynamic Branch of an Inhomogeneous Plasma
Kawasaki, Mitsuhiro; Itoh, Sanae-I.; Yagi, Masatoshi; Itoh, Kimitaka
2002-01-01
Transition phenomena between thermodynamic branch and turbulent branch in submarginal turbulent plasma are analyzed with statistical theory. Time-development of turbulent fluctuation is obtained by numerical simulations of Langevin equation which contains submarginal characteristics. Probability density functions and transition rates between two states are analyzed. Transition from turbulent branch to thermodynamic branch occurs in almost entire region between subcritical bifurcation point an...
Bound orbits and gravitational theory
Dadhich, Naresh; Ghosh, Sushant G.(School of Mathematical Sciences, University of KwaZulu-Natal, Westville, 4000, Durban, South Africa); Jhingan, Sanjay
2013-01-01
It can be easily shown that bound orbits around a static source can exist only in 4 dimension and in none else for any long range force. This is so not only for Maxwell's electromagnetic and Newton's gravity but also for Einstein's gravitation theory. In contrast to Maxwell's electrodynamics and Newton's gravity, GR has a natural higher dimensional generalization in Lovelock gravity which remarkably admits bound orbits around a static black hole in all even d=2N+2 dimensions where $N$ is degr...
Online Stochastic Matching: New Algorithms with Better Bounds
Jaillet, Patrick; Lu, Xin
2012-01-01
We consider variants of the online stochastic bipartite matching problem motivated by Internet advertising display applications, as introduced in Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. FOCS '09: Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Washington, DC), 117–126]. In this setting, advertisers express specific interests into requests for impressions of different types. Advertisers are fixed and kn...
Can the Adaptive Metropolis Algorithm Collapse Without the Covariance Lower Bound?
Vihola, Matti
2009-01-01
The Adaptive Metropolis (AM) algorithm is based on the symmetric random-walk Metropolis algorithm. The proposal distribution has the following time-dependent covariance matrix at step $n+1$ \\[ S_n = Cov(X_1,...,X_n) + \\epsilon I, \\] that is, the sample covariance matrix of the history of the chain plus a (small) constant $\\epsilon>0$ multiple of the identity matrix $I$. The lower bound on the eigenvalues of $S_n$ induced by the factor $\\epsilon I$ is theoretically convenient, but practically cumbersome, as a good value for the parameter $\\epsilon$ may not always be easy to choose. This article considers variants of the AM algorithm that do not explicitly bound the eigenvalues of $S_n$ away from zero. The behaviour of $S_n$ is studied in detail, indicating that the eigenvalues of $S_n$ do not tend to collapse to zero in general.
Bounded Densities and Their Derivatives
DEFF Research Database (Denmark)
Kozine, Igor; Krymsky, V.
2009-01-01
This paper describes how one can compute interval-valued statistical measures given limited information about the underlying distribution. The particular focus is on a bounded derivative of a probability density function and its combination with other available statistical evidence for computing...
Jorge M. S. Valente
2008-01-01
In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. We propose a lower bounding procedure based on the relaxation of the jobs' completion times. Optimal branch-and-bound algorithms are then presented. These algorithms incorporate the proposed lower bound, as well as an insertion-based dominance test.The branch-and-bound procedures are tested on a wide set of randomly generated problems. The computation...
Meyer, Ulrich; Negoescu, Andrei; Weichert, Volker
Despite disillusioning worst-case behavior, classic algorithms for single-source shortest-paths (SSSP) like Bellman-Ford are still being used in practice, especially due to their simple data structures. However, surprisingly little is known about the average-case complexity of these approaches. We provide new theoretical and experimental results for the performance of classic label-correcting SSSP algorithms on graph classes with non-negative random edge weights. In particular, we prove a tight lower bound of Ω(n 2) for the running times of Bellman-Ford on a class of sparse graphs with O(n) nodes and edges; the best previous bound was Ω(n 4/3 - ɛ ). The same improvements are shown for Pallottino's algorithm. We also lift a lower bound for the approximate bucket implementation of Dijkstra's algorithm from Ω(n logn / loglogn) to Ω(n 1.2 - ɛ ). Furthermore, we provide an experimental evaluation of our new graph classes in comparison with previously used test inputs.
Computer simulation of long-chain branching and branching indexes
Czech Academy of Sciences Publication Activity Database
Netopilík, Miloš
Vienna : University of Vienna, 2014. s. 22. [International Conference on Polymer Behaviour /6./. 22.09.2014-26.09.2014, Vienna] R&D Projects: GA ČR(CZ) GA13-02938S Institutional support: RVO:61389013 Keywords : branching indexes * intrinsic viscosity * radius of gyration Subject RIV: CD - Macromolecular Chemistry
Recursion relations and branching rules for simple Lie algebras
Lyakhovsky, V D
1995-01-01
The branching rules between simple Lie algebras and its regular (maximal) simple subalgebras are studied. Two types of recursion relations for anomalous relative multiplicities are obtained. One of them is proved to be the factorized version of the other. The factorization property is based on the existence of the set of weights \\Gamma specific for each injection. The structure of \\Gamma is easily deduced from the correspondence between the root systems of algebra and subalgebra. The recursion relations thus obtained give rise to simple and effective algorithm for branching rules. The details are exposed by performing the explicit decomposition procedure for A_{3} \\oplus u(1) \\rightarrow B_{4} injection.
An Improved Chaotic Bat Algorithm for Solving Integer Programming Problems
Directory of Open Access Journals (Sweden)
Osama Abdel Raouf
2014-08-01
Full Text Available Bat Algorithm is a recently-developed method in the field of computational intelligence. In this paper is presented an improved version of a Bat Meta-heuristic Algorithm, (IBACH, for solving integer programming problems. The proposed algorithm uses chaotic behaviour to generate a candidate solution in behaviors similar to acoustic monophony. Numerical results show that the IBACH is able to obtain the optimal results in comparison to traditional methods (branch and bound, particle swarm optimization algorithm (PSO, standard Bat algorithm and other harmony search algorithms. However, the benefits of this proposed algorithm is in its ability to obtain the optimal solution within less computation, which save time in comparison with the branch and bound algorithm (exact solution method.
Branching processes with immigration and related topics
Li, Zenghu
2006-01-01
This is a survey on recent progresses in the study of branching processes with immigration, generalized Ornstein-Uhlenbeck processes and affine Markov processes. We mainly focus on the applications of skew convolution semigroups and the connections in those processes.
Applied Aeroscience and CFD Branch Overview
LeBeau, Gerald J.; Kirk, Benjamin S.
2014-01-01
The principal mission of NASA Johnson Space Center is Human Spaceflight. In support of the mission the Applied Aeroscience and CFD Branch has several technical competencies that include aerodynamic characterization, aerothermodynamic heating, rarefied gas dynamics, and decelerator (parachute) systems.
From configurations to branched configurations and beyond
Magnot, Jean-Pierre
2013-01-01
We propose here a geometric and topological setting for the study of branching effects arising in various fields of research, e.g. in statistical mechanics and turbulence theory. We describe various aspects that appear key points to us, and finish with a limit of such a construction which stand in the dynamics on probability spaces where it seems that branching effects can be fully studied without any adaptation of the framework.
2013-03-26
... Agency Information Collection Activities; Comment Request; Upward Bound and Upward Bound Math Science... Upward Bound Math Science Annual Performance Report. OMB Control Number: 1840-NEW. Type of Review: New... under the regular Upward Bound (UB) and Upward Bound Math and Science (UBMS) Programs. The Department...
Directory of Open Access Journals (Sweden)
Chi-Jen Lin
2015-11-01
Full Text Available This study constructs a practical fuzzy three-dimensional axial assignment model, and proposes two efficient algorithms to solve the model. In our case, the model is applied to team performance management in a company to promote the performance of all members in a team. Two algorithms, namely the index-based branch and bound (B&B algorithm and the f-g trade-off algorithm, which is a hybrid of the trade-off and B&B concepts, are proposed. A numerical example is presented to illustrate these two algorithms. The computational results show that the proposed algorithms are sufficiently efficient and accurate. Two special cases are also discussed.
Higher-order Boltzmann machines and entropy bounds
Apolloni, Bruno; Battistini, Egidio; de Falco, Diego
1999-07-01
We examine some aspects of the interface area between mathematical statistics and statistical physics relevant to the study of Boltzmann machines. The Boltzmann machine learning algorithm is based on a variational principle (Gibbs' lemma for relative entropy). This fact suggests the possibility of a scheme of successive approximations: here we consider successive approximations parametrized by the order of many-body interactions among individual units. We prove bounds on the gain in relative entropy in the crucial step of adding, and estimating by Hebb's rule, a new parameter. We address the problem of providing, on the basis of local observations, upper and lower bounds on the entropy. While upper bounds are easily obtained by subadditivity, lower bounds involve localization of Hirschman bounds on a dual quantum system.
Pen Branch Delta and Savannah River Swamp Hydraulic Model
International Nuclear Information System (INIS)
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
Pen Branch Delta and Savannah River Swamp Hydraulic Model
Energy Technology Data Exchange (ETDEWEB)
Chen, K.F.
1999-05-13
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.
Mechanisms of side branching and tip splitting in a model of branching morphogenesis.
Directory of Open Access Journals (Sweden)
Yina Guo
Full Text Available Recent experimental work in lung morphogenesis has described an elegant pattern of branching phenomena. Two primary forms of branching have been identified: side branching and tip splitting. In our previous study of lung branching morphogenesis, we used a 4 variable partial differential equation (PDE, due to Meinhardt, as our mathematical model to describe the reaction and diffusion of morphogens creating those branched patterns. By altering key parameters in the model, we were able to reproduce all the branching styles and the switch between branching modes. Here, we attempt to explain the branching phenomena described above, as growing out of two fundamental instabilities, one in the longitudinal (growth direction and the other in the transverse direction. We begin by decoupling the original branching process into two semi-independent sub-processes, 1 a classic activator/inhibitor system along the growing stalk, and 2 the spatial growth of the stalk. We then reduced the full branching model into an activator/inhibitor model that embeds growth of the stalk as a controllable parameter, to explore the mechanisms that determine different branching patterns. We found that, in this model, 1 side branching results from a pattern-formation instability of the activator/inhibitor subsystem in the longitudinal direction. This instability is far from equilibrium, requiring a large inhomogeneity in the initial conditions. It successively creates periodic activator peaks along the growing stalk, each of which later on migrates out and forms a side branch; 2 tip splitting is due to a Turing-style instability along the transversal direction, that creates the spatial splitting of the activator peak into 2 simultaneously-formed peaks at the growing tip, the occurrence of which requires the widening of the growing stalk. Tip splitting is abolished when transversal stalk widening is prevented; 3 when both instabilities are satisfied, tip bifurcation occurs
Mechanisms of Side Branching and Tip Splitting in a Model of Branching Morphogenesis
Guo, Yina; Sun, Mingzhu; Garfinkel, Alan; Zhao, Xin
2014-01-01
Recent experimental work in lung morphogenesis has described an elegant pattern of branching phenomena. Two primary forms of branching have been identified: side branching and tip splitting. In our previous study of lung branching morphogenesis, we used a 4 variable partial differential equation (PDE), due to Meinhardt, as our mathematical model to describe the reaction and diffusion of morphogens creating those branched patterns. By altering key parameters in the model, we were able to reproduce all the branching styles and the switch between branching modes. Here, we attempt to explain the branching phenomena described above, as growing out of two fundamental instabilities, one in the longitudinal (growth) direction and the other in the transverse direction. We begin by decoupling the original branching process into two semi-independent sub-processes, 1) a classic activator/inhibitor system along the growing stalk, and 2) the spatial growth of the stalk. We then reduced the full branching model into an activator/inhibitor model that embeds growth of the stalk as a controllable parameter, to explore the mechanisms that determine different branching patterns. We found that, in this model, 1) side branching results from a pattern-formation instability of the activator/inhibitor subsystem in the longitudinal direction. This instability is far from equilibrium, requiring a large inhomogeneity in the initial conditions. It successively creates periodic activator peaks along the growing stalk, each of which later on migrates out and forms a side branch; 2) tip splitting is due to a Turing-style instability along the transversal direction, that creates the spatial splitting of the activator peak into 2 simultaneously-formed peaks at the growing tip, the occurrence of which requires the widening of the growing stalk. Tip splitting is abolished when transversal stalk widening is prevented; 3) when both instabilities are satisfied, tip bifurcation occurs together with side
Osada, Noriyuki; Takeda, Hiroshi
2003-01-01
To investigate crown development patterns, branch architecture, branch-level light interception, and leaf and branch dynamics were studied in saplings of a plagiotropically branching tree species, Polyalthia jenkinsii Hk. f. & Thoms. (Annonaceae) in a Malaysian rain forest. Lengths of branches and parts of the branches lacking leaves ('bare' branches) were smaller in upper branches than in lower branches within crowns, whereas lengths of 'leafy' parts and the number of leaves per branch were larger in intermediate than in upper and lower branches. Maximum diffuse light absorption (DLA) of individual leaves was not related to sapling height or branch position within crowns, whereas minimum DLA was lower in tall saplings. Accordingly, branch-level light interception was higher in intermediate than in upper and lower branches. The leaf production rate was higher and leaf loss rate was smaller in upper than in intermediate and lower branches. Moreover, the branch production rate of new first-order branches was larger in the upper crowns. Thus, leaf and branch dynamics do not correspond to branch-level light interception in the different canopy zones. As a result of architectural constraints, branches at different vertical positions experience predictable light microenvironments in plagiotropic species. Accordingly, this pattern of carbon allocation among branches might be particularly important for growth and crown development in plagiotropic species. PMID:12495920
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...
Ter-Sarkisov, Aram
2012-01-01
In this article we derive upper bounds on optimization time of the recombination algorithm solving a unimodal problem with plateaus of fitness using a tool we called Elitism Levels Traverse Mechanism. Our findings are asymptotically tight for different parameters of the algorithm and the problem, and we are able to recover some well-known bounds for test problems such as OneMax and Royal Roads. We also present find- ings on the limiting distribution of super-elite species in the population, something no-one seems to have done before in the EA community.
Bounded rationality and learning in market competition
Tuinstra, J.; Hommes, C.H.; Kopányi, D.
2015-01-01
This thesis promotes the use of bounded rationality in economic models. The assumption of perfect rationality often imposes high informational and computational burden on economic agents and predictions based on this assumption are not in line with observed behavior in some cases. Models of bounded rationality may better explain actual behavior in such situations. In the thesis we consider market models where firms are boundedly rational: they do not know the demand for their product and they...
Fuzzy upper bounds and their applications
International Nuclear Information System (INIS)
This paper considers the concept of fuzzy upper bounds and provides some relevant applications. Considering a fuzzy DEA model, the existence of a fuzzy upper bound for the objective function of the model is shown and an effective approach to solve that model is introduced. Some dual interpretations are provided, which are useful for practical purposes. Applications of the concept of fuzzy upper bounds in two physical problems are pointed out
A lower bound and estimates for resonances
International Nuclear Information System (INIS)
Using Schwinger's variational formula for the phase shifts, we deduce a lower bound for the potential strength lambdasub(l)(K) at which deltasub(l)(K)=π/2. The derivation is used to show that the lower bound is a worse estimate than a known upper bound. Whence an improved lower bound is deduced which is then used to obtain an estimate for lambdasub(l)(K). These considerations are then illustrated for some potentials of practical interest, viz., the square well, exponential, Morse and Yukawa, the results being satisfactory. (author)
Point-Based POMDP Algorithms: Improved Analysis and Implementation
Smith, Trey; Simmons, Reid
2012-01-01
Existing complexity bounds for point-based POMDP value iteration algorithms focus either on the curse of dimensionality or the curse of history. We derive a new bound that relies on both and uses the concept of discounted reachability; our conclusions may help guide future algorithm design. We also discuss recent improvements to our (point-based) heuristic search value iteration algorithm. Our new implementation calculates tighter initial bounds, avoids solving linear programs, and makes more...
An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case
Ville, Geoffroy
2013-01-01
This paper presents an optimal strategy for solving the 4 peg-7 color Mastermind MM(4,7) in the expected case (4.676) along with optimal strategies or upper bounds for other values. The program developed is using a depth-first branch and bound algorithm relying on tight upper bound, dynamic lower bound evaluation and guess equivalence to prune symmetric tree branches.
Branch Retinal Vein Occlusion and Its Management
Institute of Scientific and Technical Information of China (English)
Desmond; Archer
1992-01-01
The natural course of Branch Retinal Vein Occlusion is determined by the site and completeness of the occlusion, the integrity of arterial perfusion to the affected sector and the efficiency of the developing collateral circulation. Most patients with tributary vein occlusion have some capillary fall out and microvascular incompetence in the distribution of the affected retina and vision is significantly compromised in over 50% of patients who have either chronic macular oedema or ischemia involving the...
Gerez, Sabih H.; Heemstra de Groot, Sonia M.; Herrmann, Otto E.
1992-01-01
Rate-optimal scheduling of iterative data-flow graphs requires the computation of the iteration period bound. According to the formal definition, the total computational delay in each directed loop in the graph has to be calculated in order to determine that bound. As the number of loops cannot be expressed as a polynomial function of the number of modes in the graph, this definition cannot be the basis of an efficient algorithm. A polynomial-time algorithm for the computation of the iteratio...
Kinetics of the Formation and Dissociation of Actin Filament Branches Mediated by Arp2/3 Complex
Mahaffy, Rachel E.; Pollard, Thomas D.
2006-01-01
The actin filament network at the leading edge of motile cells relies on localized branching by Arp2/3 complex from “mother” filaments growing near the plasma membrane. The nucleotide bound to the mother filaments (ATP, ADP and phosphate, or ADP) may influence the branch dynamics. To determine the effect of the nucleotide bound to the subunits of the mother filament on the formation and stability of branches, we compared the time courses of actin polymerization in bulk samples measured using ...
[Geometry and algebra of branches of the middle cerebral artery].
Blinkov, S M
1986-01-01
A classification of the cortical branches of the middle cerebral artery (MCA) is suggested by means of which each branch in any hemisphere can be qualified and identified in any variant of MCA branching. The principle of the classification consists in grouping the branches into arteries and trunks of the second, third, etc. order. Branches supplying blood to a certain sector of the lateral surface of the hemisphere are designated arteries. Their number and zone of branching are constant. Branches giving rise to 2 and more arteries are named trunks. Branching of the trunks, the number of trunks of the second, third, etc. order, and the site and type of origin of the arteries are extremely variable. Each trunk can be designated by a formula stating its order and the name of the artery supplied by this trunk. The arrangement of the MCA branches on the surface of the gyri and deep in the sulci, represented on the map of the lateral surface of the hemisphere, is designated conditionally as geometry of MCA branches. The order of branching of the trunks and the type of origin of the arteries, represented on abstract maps of the lateral surface of the hemisphere, are designated conditionally as algebra of the MCA branches. The variability of the geometry and algebra of the MCA branches must be taken into consideration in operations for extra-intracranial microanastomosis and in endovasal intervention on the MCA. PMID:3811741
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.
Verifying Resource Bounds of Programs with Lazy Evaluation and Memoization
Madhavan, Ravichandhran; Kuncak, Viktor
2016-01-01
We present a new approach for specifying and verifying resource utilization of functional programs that use lazy evaluation and memoization. Our approach verifies asymptotically tight bounds of complex programs that rely on deep sharing and aliasing of lazy heap references, as well as algorithms that use memoization extensively. Our approach can also find counter-examples for incorrect specifications or implementations. We demonstrate the effectiveness of the approach by verifying the resou...
A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs
Dinneen, Michael J.; Khosravani, Masoud
We consider the Minimum Spanning Caterpillar Problem (MSCP) in a graph where each edge has two costs, spine (path) cost and leaf cost, depending on whether it is used as a spine or a leaf edge. The goal is to find a spanning caterpillar in which the sum of its edge costs is the minimum. We show that the problem has a linear time algorithm when a tree decomposition of the graph is given as part of the input. Despite the fast growing constant factor of the time complexity of our algorithm, it is still practical and efficient for some classes of graphs, such as outerplanar, series-parallel (K 4 minor-free), and Halin graphs. We also briefly explain how one can modify our algorithm to solve the Minimum Spanning Ring Star and the Dual Cost Minimum Spanning Tree Problems.
40 CFR 721.10094 - Decene, branched and linear.
2010-07-01
... 40 Protection of Environment 30 2010-07-01 2010-07-01 false Decene, branched and linear. 721.10094... Substances § 721.10094 Decene, branched and linear. (a) Chemical substance and significant new uses subject to reporting. (1) The chemical substance identified as decene, branched and linear (PMN P-03-272;...
Organization and targets of the European Branch
Energy Technology Data Exchange (ETDEWEB)
Cataldi, R.
1997-12-01
After a short historical review of the formation, objectives and organization of the International Geothermal Association (IGA), this paper describes the functions, goals and activities of the IGA European Branch. In particular, the paper illustrates the plan of action established for the periods 1993-`95 and 1996-`98, and the issues dealt with by the European Forum as of August 1996. The last section of the paper outlines the main problems to be faced in the near future in order to facilitate the aggregation of efforts, the amalgamation of promotional initiatives and the coordination of the basic activities needed for the consolidation and growth of the geothermal community in Europe. (orig.)
Mutually Unbiased Bases and Bound Entanglement
Hiesmayr, Beatrix C.; Löffler, Wolfgang
2013-01-01
In this contribution we relate two different key concepts: mutually unbiased bases (MUBs) and entanglement; in particular we focus on bound entanglement, i.e. highly mixed states which cannot be distilled by local operations and classical communications. For a certain class of states --for which the state-space forms a "magic" simplex-- we analyze the set of bound entangled states detected by the MUB criterion for different dimensions d and number of particles n. We find that the geometry is ...
Logic, planning agency and branching time
Ricardo Souza Silvestre
2010-01-01
The purpose of this paper is to give a formal account of a kind of agency so far neglected in the field of philosophical modal logic of action: planning agency. In doing this we follow the standard approach of modal logics of agency exemplified by the works of Belnap, Chellas and Pörn. Since we believe there is a close relation between planning, time and indeterminism, we use the theory of branching time as a conceptual framework for investigating the basic features of planning agency. Beside...
Daneshgaran, F; Mondin, M
2007-01-01
This article proposes a novel iterative algorithm based on Low Density Parity Check (LDPC) codes for compression of correlated sources at rates approaching the Slepian-Wolf bound. The setup considered in the article looks at the problem of compressing one source at a rate determined based on the knowledge of the mean source correlation at the encoder, and employing the other correlated source as side information at the decoder which decompresses the first source based on the estimates of the actual correlation. We demonstrate that depending on the extent of the actual source correlation estimated through an iterative paradigm, significant compression can be obtained relative to the case the decoder does not use the implicit knowledge of the existence of correlation.
A Forward Reachability Algorithm for Bounded Timed-Arc Petri Nets
DEFF Research Database (Denmark)
David, Alexandre; Jacobsen, Lasse; Jacobsen, Morten;
2012-01-01
the presence of monotonicity-breaking features like age invariants and inhibitor arcs. We implement the algorithm within the model-checkerTAPAAL and the experimental results document an encouraging performance compared to verification approaches that translate TAPN models to UPPAAL timed automata....
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...... show: 𝒞 is d-space learnable if and only if the compression parameter of 𝒞 is at most d. This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches, for example, by Floyd, who presents consistent space bounded learning algorithms, but has to...
An Algorithm for Checking Regularity of Interval Matrices
Czech Academy of Sciences Publication Activity Database
Jansson, C.; Rohn, Jiří
1999-01-01
Roč. 20, č. 3 (1999), s. 756-776. ISSN 0895-4798 R&D Projects: GA ČR GA201/98/0222 Institutional research plan: AV0Z1030915 Keywords : interval matrix * regularity * singularity * algorithm * branch - and - bound * linear interval equations * linear programming Subject RIV: BA - General Mathematics Impact factor: 0.663, year: 1999
DEFF Research Database (Denmark)
Hansen, Anders Dohn; Kolind, Esben; Clausen, Jens
2009-01-01
. 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 instances. The main contribution of this article is the addition of synchronization between teams in an exact optimization context....
DEFF Research Database (Denmark)
Hansen, Anders Dohn; Kolind, Esben; Clausen, Jens
. 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 instances. The main contribution of this article is the addition of synchronization between teams in an exact optimization context....
Branching structure for an (L-1) random walk in random environment and its applications
Hong, Wenming
2010-01-01
By decomposing the random walk path, we construct a multitype branching process with immigration in random environment for corresponding random walk with bounded jumps in random environment. Then we give two applications of the branching structure. Firstly, we specify the explicit invariant density by a method different with the one used in Br\\'emont [3] and reprove the law of large numbers of the random walk by a method known as the environment viewed from particles". Secondly, the branching structure enables us to prove a stable limit law, generalizing the result of Kesten-Kozlov-Spitzer [11] for the nearest random walk in random environment. As a byproduct, we also prove that the total population of a multitype branching process in random environment with immigration before the first regeneration belongs to the domain of attraction of some \\kappa -stable law.
Data streams algorithms and applications
Muthukrishnan, S
2014-01-01
Data stream algorithms as an active research agenda emerged only over the past few years, even though the concept of making few passes over the data for performing computations has been around since the early days of Automata Theory. The data stream agenda now pervades many branches of Computer Science including databases, networking, knowledge discovery and data mining, and hardware systems. Industry is in synch too, with Data Stream Management Systems (DSMSs) and special hardware to deal with data speeds. Even beyond Computer Science, data stream concerns are emerging in physics, atmospheric
Quantum Computation and Algorithms
International Nuclear Information System (INIS)
It is now firmly established that quantum algorithms provide a substantial speedup over classical algorithms for a variety of problems, including the factorization of large numbers and the search for a marked element in an unsorted database. In this talk I will review the principles of quantum algorithms, the basic quantum gates and their operation. The combination of superposition and interference, that makes these algorithms efficient, will be discussed. In particular, Grover's search algorithm will be presented as an example. I will show that the time evolution of the amplitudes in Grover's algorithm can be found exactly using recursion equations, for any initial amplitude distribution
Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems
Fukunaga, A S; 10.1613/jair.2106
2011-01-01
Many combinatorial optimization problems such as the bin packing and multiple knapsack problems involve assigning a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systms, and can also be found as subproblems of scheduling problems. We propose bin completion, a branch-and-bound strategy for one-dimensional, multicontainer packing problems. Bin completion combines a bin-oriented search space with a powerful dominance criterion that enables us to prune much of the space. The performance of the basic bin completion framework can be enhanced by using a number of extensions, including nogood-based pruning techniques that allow further exploitation of the dominance criterion. Bin completion is applied to four problems: multiple knapsack, bin covering, min-cost covering, and bin packing. We show that our bin completion algorithms yield new, state-of-the-art results for the multiple knapsack, bin covering,...
A PSL Bounded Model Checking Method
Institute of Scientific and Technical Information of China (English)
YU Lei; ZHAO Zongtao
2012-01-01
SAT-based bounded model checking （BMC） is introduced as an important complementary technique to OBDD-based symbolic model checking, and is an efficient verification method for parallel and reactive systems. However, until now the properties verified by bounded model checking are very finite. Temporal logic PSL is a property specification language （IEEE-1850） describing parallel systems and is divided into two parts, i.e. the linear time logic FL and the branch time logic OBE. In this paper, the specification checked by BMC is extended to PSL and its algorithm is also proposed. Firstly, define the bounded semantics of PSL, and then reduce the bounded semantics into SAT by translating PSL specification formula and the state transition relation of the system to the propositional formula A and B, respectively. Finally, verify the satisfiability of the conjunction propositional formula of A and B. The algorithm results in the translation of the existential model checking of the temporal logic PSL into the satisfiability problem of propositional formula. An example of a queue controlling circuit is used to interpret detailedly the executing procedure of the algorithm.
An ant colony algorithm for the sequential testing problem under precedence constraints
Çatay, Bülent; Catay, Bulent; Özlük, Özgür; Ozluk, Ozgur; Ünlüyurt, Tonguç; Unluyurt, Tonguc
2008-01-01
We consider the problem of minimum cost sequential testing of a series (parallel) system under precedence constraints that can be modeled as a nonlinear integer program. We develop and implement an ant colony algorithm for the problem. We demonstrate the performance of this algorithm for special type of instances for which the optimal solutions can be found in polynomial time. In addition, we compare the performance of the algorithm with a special branch and bound algo...
Geology of the Cane Branch and Helton Branch watershed areas, McCreary County, Kentucky
Lyons, Erwin J.
1957-01-01
Cane Branch and Helton Branch in McCreary County, Kentucky, are about 1.4 miles apart (fig. 1). Can Branch, which is about 2.1 miles long, emptied into Hughes Fork of Beaver Creek. Its watershed area of about 1.5 square miles lies largely in the Wiborf 7 1/2-minute quadrangle (SW/4 Cumberland Falls 15-minute quadrangle), but the downstream part of the area extends northward into the Hail 7 1/2-minute quadrangle (NW/4 Cumberland Falls 15-minute quadrangle). Helton Branch, which is about 1.1 miles long, has two tributaries and empties into Little Hurricane Fork of Beaver Creek. It drains an area of about 0.8 square mile of while about 0.5 square mile is in the Hail quadrangle and the remainder in the Wilborg quadrangle. The total relief in the Can Branch area is about 500 feet and in the Helton Branch area about 400 feet. Narrow, steep-sided to canyon-like valley and winding ridges, typical of the Pottsville escarpment region, are characteristic of both areas. Thick woods and dense undergrowth cover much of the two areas. Field mapping was done on U.S. Geological Survey 7 1/2-minute maps having a scale of 1:24,000 and a contour interval of 20 feet. Elevations of lithologic contacts were determined with a barometer and a hand level. Aerial photographs were used principally to trace the cliffs formed by sandstone and conglomerate ledges. Exposures, except for those of the cliff- and ledge-forming sandstone and conglomerates, are not abundant. The most complete stratigraphic sections (secs. 3 and 4, fig. 2) in the two areas are exposed in cuts of newly completed Forest Service roads, but the rick in the upper parts of the exposures is weathered. To supplement these sections, additional sections were measured in cuts along the railroad and main highways in nor near the watersheds.
Shaik, Shahnoor S.; Obata, Toshihiro; Hebelstrup, Kim H.; Schwahn, Kevin; Fernie, Alisdair R.; Mateiu, Ramona Valentina; Blennow, Andreas
2016-01-01
Starch is of fundamental importance for plant development and reproduction and its optimized molecular assembly is potentially necessary for correct starch metabolism. Re-structuring of starch granules in-planta can therefore potentially affect plant metabolism. Modulation of granule micro-structure was achieved by decreasing starch branching and increasing starch-bound phosphate content in the barley caryopsis starch by RNAi suppression of all three Starch Branching Enzyme (SBE) isoforms or ...
HiggsBounds: Confronting arbitrary Higgs sectors with exclusion bounds from LEP and the Tevatron
Bechtle, P.; Brein, O.; Heinemeyer, S.; Weiglein, G.; Williams, K. E.
2010-01-01
HiggsBounds is a computer code that tests theoretical predictions of models with arbitrary Higgs sectors against the exclusion bounds obtained from the Higgs searches at LEP and the Tevatron. The included experimental information comprises exclusion bounds at 95% C.L. on topological cross sections. In order to determine which search topology has the highest exclusion power, the program also includes, for each topology, information from the experiments on the expected exclusion bound, which would have been observed in case of a pure background distribution. Using the predictions of the desired model provided by the user as input, HiggsBounds determines the most sensitive channel and tests whether the considered parameter point is excluded at the 95% C.L. HiggsBounds is available as a Fortran 77 and Fortran 90 code. The code can be invoked as a command line version, a subroutine version and an online version. Examples of exclusion bounds obtained with HiggsBounds are discussed for the Standard Model, for a model with a fourth generation of quarks and leptons and for the Minimal Supersymmetric Standard Model with and without CP-violation. The experimental information on the exclusion bounds currently implemented in HiggsBounds will be updated as new results from the Higgs searches become available.
Bounds for graph regularity and removal lemmas
Conlon, David
2011-01-01
We show, for any positive integer k, that there exists a graph in which any equitable partition of its vertices into k parts has at least ck^2/\\log^* k pairs of parts which are not \\epsilon-regular, where c,\\epsilon>0 are absolute constants. This bound is tight up to the constant c and addresses a question of Gowers on the number of irregular pairs in Szemer\\'edi's regularity lemma. In order to gain some control over irregular pairs, another regularity lemma, known as the strong regularity lemma, was developed by Alon, Fischer, Krivelevich, and Szegedy. For this lemma, we prove a lower bound of wowzer-type, which is one level higher in the Ackermann hierarchy than the tower function, on the number of parts in the strong regularity lemma, essentially matching the upper bound. On the other hand, for the induced graph removal lemma, the standard application of the strong regularity lemma, we find a different proof which yields a tower-type bound. We also discuss bounds on several related regularity lemmas, inclu...
Command and Data Handling Branch Internship
Billings, Rachel Mae
2016-01-01
Modular Integrated Stackable Layers (MISL) is a computer system designed for simple, fast, and cost effective flexible reconfiguration in space environments such as the ISS and Orion projects for various uses. Existing applications include wireless and wired communications, data acquisition and instrumentation, and camera systems, and potential applications include bus protocol converters and subsystem control. MISL is based on Texas Instruments (TI)' MSP430 16-bit ultra-low-power microcontroller device. The purpose of my project was to integrate the MISL system with a liquid crystal display (LCD) touchscreen. The LCD, manufactured by Crystalfontz and part number CFAF320240F-035T-TS, is a 320 by 240 RGB resistive color screen including an optional carrier board. The vast majority of the project was done with Altium Designer, a tool for printed circuit board (PCB) schematic capture, 3D design, and FPGA (Field Programmable Gate Array) development. The new PCB was to allow the LCD to directly stack to the rest of MISL. Research was done with datasheets for the TI microcontroller and touchscreen display in order to meet desired hardware specifications. Documentation on prior MISL projects was also utilized. The initial step was to create a schematic for the LCD, power bus, and data bus connections between components. A layout was then designed with the required physical dimensions, routed traces and vias, power and ground planes, layer stacks, and other specified design rules such as plane clearance and hole size. Multiple consultation sessions were held with Hester Yim, the technical discipline lead for the Command and Data Handling Branch, and Christy Herring, the lead PCB layout designer in the Electronic Design and Manufacturing Branch in order to ensure proper configuration. At the moment, the PCB is awaiting revision by the latter-mentioned branch. Afterwards, the board will begin to undergo the manufacturing and testing process. Throughout the internship at
Correlation Distance and Bounds for Mutual Information
Directory of Open Access Journals (Sweden)
Michael J. W. Hall
2013-09-01
Full Text Available The correlation distance quantifies the statistical independence of two classical or quantum systems, via the distance from their joint state to the product of the marginal states. Tight lower bounds are given for the mutual information between pairs of two-valued classical variables and quantum qubits, in terms of the corresponding classical and quantum correlation distances. These bounds are stronger than the Pinsker inequality (and refinements thereof for relative entropy. The classical lower bound may be used to quantify properties of statistical models that violate Bell inequalities. Partially entangled qubits can have lower mutual information than can any two-valued classical variables having the same correlation distance. The qubit correlation distance also provides a direct entanglement criterion, related to the spin covariance matrix. Connections of results with classically-correlated quantum states are briefly discussed.
Weakly bound systems, continuum effects, and reactions
Jaganathen, Y; Ploszajczak, M
2012-01-01
Structure of weakly bound/unbound nuclei close to particle drip lines is different from that around the valley of beta stability. A comprehensive description of these systems goes beyond standard Shell Model and demands an open quantum system description of the nuclear many-body system. We approach this problem using the Gamow Shell Model which provides a fully microscopic description of bound and unbound nuclear states, nuclear decays, and reactions. We present in this paper the first application of the GSM for a description of the elastic and inelastic scattering of protons on 6He.
Czech Academy of Sciences Publication Activity Database
Koldovský, Zbyněk; Tichavský, Petr; Oja, E.
2006-01-01
Roč. 17, č. 5 (2006), s. 1265-1277. ISSN 1045-9227 R&D Projects: GA MŠk 1M0572 Institutional research plan: CEZ:AV0Z10750506 Keywords : Independent component analysis * blind source separation * blind deconvolution * Cramer-Rao lower bound * algorithm FastICA Subject RIV: BB - Applied Statistics, Operational Research Impact factor: 2.620, year: 2006
Self adaptive solution strategies: Locally bound constrained Newton Raphson solution algorithms
Padovan, Joe
1991-01-01
A summary is given of strategies which enable the automatic adjustment of the constraint surfaces recently used to extend the range and numerical stability/efficiency of nonlinear finite element equation solvers. In addition to handling kinematic and material induced nonlinearity, both pre-and postbuckling behavior can be treated. The scheme employs localized bounds on various hierarchical partitions of the field variables. These are used to resize, shape, and orient the global constraint surface, thereby enabling essentially automatic load/deflection incrementation. Due to the generality of the approach taken, it can be implemented in conjunction with the constraints of an arbitrary functional type. To benchmark the method, several numerical experiments are presented. These include problems involving kinematic and material nonlinearity, as well as pre- and postbuckling characteristics. Also included is a list of papers published in the course of the work.
Entropy Bounds, Holographic Principle and Uncertainty Relation
Directory of Open Access Journals (Sweden)
I. V. Volovich
2001-06-01
Full Text Available Abstract: A simple derivation of the bound on entropy is given and the holographic principle is discussed. We estimate the number of quantum states inside space region on the base of uncertainty relation. The result is compared with the Bekenstein formula for entropy bound, which was initially derived from the generalized second law of thermodynamics for black holes. The holographic principle states that the entropy inside a region is bounded by the area of the boundary of that region. This principle can be called the kinematical holographic principle. We argue that it can be derived from the dynamical holographic principle which states that the dynamics of a system in a region should be described by a system which lives on the boundary of the region. This last principle can be valid in general relativity because the ADM hamiltonian reduces to the surface term.
Torons and D-Brane Bound States
Guralnik, Z.; Ramgoolam, S.
1997-01-01
We interpret instantons on a torus with twisted boundary conditions, in terms of bound states of branes. The interplay between the SU(N) and U(1) parts of the U(N) theory of N 4-branes allows the construction of a variety of bound states. The SU(N) and U(1) parts can contribute fractional amounts to the total instanton number which is integral. The geometry of non-self intersecting two-cycles in $T^4$ sheds some light on a number of properties of these solutions.
Vulnerable Derivatives and Good Deal Bounds
DEFF Research Database (Denmark)
Murgoci, Agatha
2013-01-01
We price vulnerable derivatives – i.e. derivatives where the counterparty may default. These are basically the derivatives traded on the over-the-counter (OTC) markets. Default is modelled in a structural framework. The technique employed for pricing is good deal bounds (GDBs). The method imposes a...... can be obtained. We provide a link between the objective probability measure and the range of potential risk-neutral measures, which has an intuitive economic meaning. We also provide tight pricing bounds for European calls and show how to extend the call formula to pricing other financial products in...
The Lovasz bound and some generalizations
Mceliece, R. J.; Rodemich, E. R.; Rumsey, H. C., Jr.
1978-01-01
The zero error capacity of a discrete memoryless channel is defined as the largest rate at which information can be transmitted over the channel with zero error probability. One channel with five inputs and outputs whose zero capacity remained unsolved until very recently is considered. An extremely powerful and general technique phased in terms of graph theory, for studying combinatorial packing problems is presented. In particular, Delsarte's linear programming bound for cliques in association schemes appears as a special case of the Lovasz bound.
Creed, Peter A.; Patton, Wendy; Hood, Michelle
2010-01-01
We surveyed 506 Australian high school students on career development (exploration, planning, job-knowledge, decision-making, indecision), personal functioning (well-being, self-esteem, life satisfaction, school satisfaction) and control variables (parent education, school achievement), and tested differences among work-bound, college-bound and…
Learning within bounds and dream sleep
Geszti, T.; Pazmandi, F.
1987-12-01
In a bounded-synapses version of Hopfield's model (1984) for neural networks the quasienergy of a given memory, which is approximately equal to the depth of the corresponding energy well is calculated exactly by treating the change of a synaptic strength on learning as a random walk within bounds. Attractors corresponding to stored memories are found to be considerably flattened before serious retrieval errors arise. This allows dream sleep to be interpreted as random recall and relearning of fresh strong memories, in order to stack them on top of weak incidental memory imprints of a day.
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.
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 ...
Monotonicity and bounds on Bessel functions
Directory of Open Access Journals (Sweden)
Larry Landau
2000-07-01
Full Text Available survey my recent results on monotonicity with respect to order of general Bessel functions, which follow from a new identity and lead to best possible uniform bounds. Application may be made to the "spreading of the wave packet" for a free quantum particle on a lattice and to estimates for perturbative expansions.
Deregulation of Bank Entry and Branching: Impact on Competition
Milo, Melanie S.
2001-01-01
This paper looks at public policy towards bank entry and branching in the Philippines and its impact on the sectors structure, conduct and performance. In particular, it argues that regulatory restrictions on bank entry and branching have had adverse effects on competition, while the liberalization of these restrictions have led to a more competitive banking sector. The paper has two main sections. Section II presents the history of regulation of bank entry and branching in the Philippines. ...
Improved bounds in Weaver and Feichtinger Conjectures
Bownik, Marcin; Casazza, Peter G.; Marcus, Adam W.; Speegle, Darrin
2015-01-01
We sharpen the constant in the $KS_2$ conjecture of Weaver \\cite{We}, which was validated by Marcus, Spielman, and Srivastava \\cite{MSS} in their solution of the Kadison--Singer problem. We then apply this result to prove optimal asymptotic bounds on the size of partitions in the Feichtinger conjecture.
On Quantum Capacity and its Bound
Ohya, Masanori; Volovich, Igor V.
2004-01-01
The quantum capacity of a pure quantum channel and that of classical-quantum-classical channel are discussed in detail based on the fully quantum mechanical mutual entropy. It is proved that the quantum capacity generalizes the so-called Holevo bound.
Evolutionary Computation Algorithms for Cryptanalysis: A Study
Garg, Poonam
2010-01-01
The cryptanalysis of various cipher problems can be formulated as NP-Hard combinatorial problem. Solving such problems requires time and/or memory requirement which increases with the size of the problem. Techniques for solving combinatorial problems fall into two broad groups - exact algorithms and Evolutionary Computation algorithms. An exact algorithms guarantees that the optimal solution to the problem will be found. The exact algorithms like branch and bound, simplex method, brute force etc methodology is very inefficient for solving combinatorial problem because of their prohibitive complexity (time and memory requirement). The Evolutionary Computation algorithms are employed in an attempt to find an adequate solution to the problem. A Evolutionary Computation algorithm - Genetic algorithm, simulated annealing and tabu search were developed to provide a robust and efficient methodology for cryptanalysis. The aim of these techniques to find sufficient "good" solution efficiently with the characteristics ...
University Competition and Transnational Education: The Choice of Branch Campus
Joanna Poyago-Theotoky; Alessandro Tampieri
2015-01-01
We present a theoretical framework in which an elitist and a non- elitist university in a developed country compete by choosing their admission standards and deciding whether or not to open a branch campus in a developing country. Students from a developing country attend university either if a branch campus is opened or if they can afford to move to the developed country. We characterise the equi- libria by focussing on the relationship between the investment costs of a branch campus and the...
Preventing Death and Serious Injury from Falling Trees and Branches
Brookes, Andrew
2007-01-01
Of 128 outdoor education related deaths examined since 1960, 14 have been due to falling trees or branches. This article examines the grounds on which death or serious injury due to falling trees or branches can be regarded as an inherent risk in outdoor education, and the extent to which such incidents can be regarded as preventable. It compares…
Branching ratio change in K- absorption at rest and the nature of the Λ(1405)
International Nuclear Information System (INIS)
We investigate in-medium corrections to the branching ratio in K- absorption at rest and their effect on the charged pion π± spectrum. The in-medium corrections are due to Pauli blocking, which arises if the Λ(1405) is assumed to be a bar K-nucleon bound state and leads to a density- and momentum-dependent mass shift of the Λ(1405). Requiring that the optical potential and the branching ratio are derived from the same elementary T matrix, we find that the in-medium corrected, density-dependent T matrix gives a better description of the K- absorption reaction than the free, density-independent one. This result suggests that the dominant component of the Λ(1405) wave function is the bar KN bound state. copyright 1997 The American Physical Society
[Variability of the celiac artery and its branches in sheep].
Karmona, Kh; Kovachev, G
1985-01-01
Contrast matter was used with a total of 363 sheep fetuses, newborn lambs, and adult sheep to study the variability of the coeliac artery and its branches. It was found that the artery and some of its branches, such as arteria ruminalis sinistra, arteria reticularis, and arteria lienalis often showed variations, resp., deviations in their branching and distribution. Others, such as arteria ruminalis dextra and arteria hepatica showed no variations whatever. Both the coeliac artery and the anterior intestinal artery in the sheep were most often shown to branch from the aorta alone (in 71.07 per cent of the cases) as against the rarely observed common truncus coeliacomesentericus (in 28.93 per cent of the cases). The most commonly observed form of branching of arteria coeliaca seemed to be tripus coeliacus, while the branching with the formation of a short truncus hepatogastricus was comparatively a rare phenomenon. It was also established that the left ruminal artery was much more frequently the branch of truncus lienoruminalis than the branch of arteria gastrica sinistra. So far as the place in which arteria reticularis arose three variants were observed. Most frequently this artery was shown to be the branch of arteria gastrica sinistra. PMID:4013078
Branch structure of corona discharge: experimental simulation and chemical properties
International Nuclear Information System (INIS)
The branch structure of corona discharge has been investigated via C2H2 corona discharge. Carbon filament with excellent branch structure is formed in the discharge. This carbon filament offers a direct mimic of the branch structure of corona discharge. It provides a very useful way to study on the average energy, physical and chemical characteristics of corona discharge. On this basis, the chemical property of corona discharge for methane conversion is discussed. (authors)
模具零件的最小包围盒生成算法%Generation algorithm of minimum bounding box for die & mould components
Institute of Scientific and Technical Information of China (English)
孔垂品; 牛强; 柳伟; 周雄辉
2014-01-01
提出一种实用的最小包围盒算法，将任意位置的复杂三维模型投影在3个主平面上，通过分析投影外轮廓的最小包围矩形来最终确定三维模型的最小包围盒。算法不再采用传统算法中旋转模型的方法，而根据旋转投影的外轮廓来确定最小包围盒，提高了算法的效率。同时算法通过分析识别模型的基本形状，将其分为箱体类、回转类和异形类，以快速确定一个主投影方向，将三维问题转化为求二维平面上的最小包围矩形，进一步提高了计算效率。算法可以嵌入NX等商用CAD系统，经过大量测试对比，相对传统算法更高效，并且稳定可靠，可广泛应用于任意位置的复杂模具零件的生成和干涉检查等。%A practical algorithm of minimum bounding box was proposed in which a com-plex 3D model at arbitrary position is projected on three principal planes; and then the minimum bounding box of the 3D model is determined by analyzing the minimum bound-ing rectangle of outer contour projection. The algorithm no longer uses the rotating model in traditional method; the minimum bounding box is determined according to the outer con-tour of rotating projection to improve the efficiency. The algorithm classifies the basic shape of models as box type, rotary type and abnormal type to rapidly determine a main direction of projection. It translates the 3D problem into the minimum bounding rectangle on 2D plane to further improve the computational efficiency. The algorithm can be implant-ed in the commercial CAD system such as NX and so on. The application can be in the blank generation and interference checking of complex die & mould components at arbi-trary position.
Solving Integer Programming Problems by Using Artificial Bee Colony Algorithm
Akay, Bahriye; Karaboga, Dervis
This paper presents a study that applies the Artificial Bee Colony algorithm to integer programming problems and compares its performance with those of Particle Swarm Optimization algorithm variants and Branch and Bound technique presented to the literature. In order to cope with integer programming problems, in neighbour solution production unit, solutions are truncated to the nearest integer values. The experimental results show that Artificial Bee Colony algorithm can handle integer programming problems efficiently and Artificial Bee Colony algorithm can be considered to be very robust by the statistics calculated such as mean, median, standard deviation.
Energy additivity in branched and cyclic hydrocarbons
Energy Technology Data Exchange (ETDEWEB)
Gao, H.; Bader, R.F.W. [McMaster Univ., Hamilton, ON (Canada). Dept. of Chemistry; Cortes-Guzman, F. [Univ. Nacional Autonoma de Mexico, (Mexico). Dept. de Fisicoquimica
2009-11-15
This paper reported on a study of the energetic relationships between hydrocarbon molecules and the heats of formation. The quantum theory of atoms in molecules (QTAIM) was used to investigate the degree to which branched hydrocarbons obey a group additivity scheme for energy and populations. The QTAIM defined the properties of the chemical groups. The experimental and theoretical transferability of the methyl and methylene groups of the linear hydrocarbons was also explored. The calculations were performed using a large basis set at the restricted Hartree-Fock and MP2(full) levels of theory. The study also investigated the deviations from additivity, noted for small ring hydrocarbons leading to the definition of strain energy. The QTAIM energies recovered the experimental values. The paper included details regarding the delocalization of the electron density over the surface of the cyclopropane ring, responsible for its homoaromatic properties. The calculations presented in this study satisfied the virial theorem for the atomic definition of energy. The paper discussed the problems associated with the use of the density functional theory (DFT) resulting from its failure to satisfy the virial theorem. 44 refs., 9 tabs., 2 figs.
HiggsBounds: Confronting Arbitrary Higgs Sectors with Exclusion Bounds from LEP and the Tevatron
Bechtle, Philip; Heinemeyer, Sven; Weiglein, Georg; Williams, Karina E
2008-01-01
HiggsBounds is a computer code that tests theoretical predictions of models with arbitrary Higgs sectors against the exclusion bounds obtained from the Higgs searches at LEP and the Tevatron. The included experimental information comprises exclusion bounds at 95% C.L. on topological cross sections. In order to determine which search topology has the highest exclusion power, the program also includes, for each topology, information from the experiments on the expected exclusion bound, which would have been observed in case of a pure background distribution. Using the predictions of the desired model provided by the user as input, HiggsBounds determines the most sensitive channel and tests whether the considered parameter point is excluded at the 95% C.L. HiggsBounds is available as a Fortran 77 and Fortran 90 code. The code can be invoked as a command line version, a subroutine version and an online version. Examples of exclusion bounds obtained with HiggsBounds are discussed for a model with a fourth generati...
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...
Directory of Open Access Journals (Sweden)
Chansiri Singhtaun
2010-01-01
Full Text Available Problem statement: The objective of this study is to develop efficient exact algorithms for a single source capacitated multi-facility location problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the two dimensional plane to satisfy the demand of n customers with minimum total transportation cost which is proportional to the rectilinear distance between the facilities and their customers. Approach: Two exact algorithms are proposed and compared. The first algorithm, decomposition algorithm, uses explicit branching on the allocation variables and then solve for location variable corresponding to each branch as the original Mixed Integer Programming (MIP formulation with nonlinear objective function of the problem. For the other algorithm, the new formulation of the problem is first created by making use of a well-known condition for the optimal facility locations. The problem is considered as a p-median problem and the original formulation is transformed to a binary integer programming problem. The classical exact algorithm based on this formulation which is branch-and-bound algorithm (implicit branching is then used. Results: Computational results show that decomposition algorithm can provide the optimum solution for larger size of the studied problem with much less processing time than the implicit branching on the discrete reformulated problem. Conclusion: The decomposition algorithm has a higher efficiency to deal with the studied NP-hard problems but is required to have efficient MIP software to support.
Identities and exponential bounds for transfer matrices
International Nuclear Information System (INIS)
This paper is about analytic properties of single transfer matrices originating from general block-tridiagonal or banded matrices. Such matrices occur in various applications in physics and numerical analysis. The eigenvalues of the transfer matrix describe localization of eigenstates and are linked to the spectrum of the block tridiagonal matrix by a determinantal identity. If the block tridiagonal matrix is invertible, it is shown that half of the singular values of the transfer matrix have a lower bound exponentially large in the length of the chain, and the other half have an upper bound that is exponentially small. This is a consequence of a theorem by Demko, Moss and Smith on the decay of matrix elements of the inverse of banded matrices. This article is part of a special issue of Journal of Physics A: Mathematical and Theoretical devoted to ‘Lyapunov analysis: from dynamical systems theory to applications’. (paper)
Mutual information rate and bounds for it.
Directory of Open Access Journals (Sweden)
Murilo S Baptista
Full Text Available The amount of information exchanged per unit of time between two nodes in a dynamical network or between two data sets is a powerful concept for analysing complex systems. This quantity, known as the mutual information rate (MIR, is calculated from the mutual information, which is rigorously defined only for random systems. Moreover, the definition of mutual information is based on probabilities of significant events. This work offers a simple alternative way to calculate the MIR in dynamical (deterministic networks or between two time series (not fully deterministic, and to calculate its upper and lower bounds without having to calculate probabilities, but rather in terms of well known and well defined quantities in dynamical systems. As possible applications of our bounds, we study the relationship between synchronisation and the exchange of information in a system of two coupled maps and in experimental networks of coupled oscillators.
Mutual information rate and bounds for it.
Baptista, Murilo S; Rubinger, Rero M; Viana, Emilson R; Sartorelli, José C; Parlitz, Ulrich; Grebogi, Celso
2012-01-01
The amount of information exchanged per unit of time between two nodes in a dynamical network or between two data sets is a powerful concept for analysing complex systems. This quantity, known as the mutual information rate (MIR), is calculated from the mutual information, which is rigorously defined only for random systems. Moreover, the definition of mutual information is based on probabilities of significant events. This work offers a simple alternative way to calculate the MIR in dynamical (deterministic) networks or between two time series (not fully deterministic), and to calculate its upper and lower bounds without having to calculate probabilities, but rather in terms of well known and well defined quantities in dynamical systems. As possible applications of our bounds, we study the relationship between synchronisation and the exchange of information in a system of two coupled maps and in experimental networks of coupled oscillators. PMID:23112809
Locating dominating codes: Bounds and extremal cardinalities
Cáceres, José; Mora, Mercè; Pelayo, Ignacio M; Puertas, María Luz
2012-01-01
In this work, two types of codes such that they both dominate and locate the vertices of a graph are studied. Those codes might be sets of detectors in a network or processors controlling a system whose set of responses should determine a malfunctioning processor or an intruder. Here, we present our more significant contributions on \\lambda-codes and \\eta-codes concerning concerning bounds, extremal values and realization theorems.
39 CFR 241.2 - Stations and branches.
2010-07-01
... Service UNITED STATES POSTAL SERVICE ORGANIZATION AND ADMINISTRATION ESTABLISHMENT CLASSIFICATION, AND DISCONTINUANCE § 241.2 Stations and branches. (a) Description. (1) Stations are established within the corporate limits or boundary, and branches are established outside the corporate limits or boundary of the...
Tsirelson's bound and supersymmetric entangled states
Borsten, L; Duff, M J
2012-01-01
In order to see whether superqubits are more nonlocal than ordinary qubits, we construct a class of two-superqubit entangled states as a nonlocal resource in the CHSH game. Since super Hilbert space amplitudes are Grassmann numbers, the result depends on how we extract real probabilities and we examine three choices of map: (1) DeWitt (2) Trigonometric (3) Modified Rogers. In cases (1) and (2) the winning probability reaches the Tsirelson bound p(win) = cos^2 pi/8 \\simeq 0.8536 of standard quantum mechanics. Case (3) crosses Tsirelson's bound with p(win) = 0.9265. Although all states used in the game involve probabilities lying between 0 and 1, case (3) permits other changes of basis inducing negative transition probabilities.
Moment Problems on Bounded and Unbounded Domains
Directory of Open Access Journals (Sweden)
Octav Olteanu
2013-01-01
Full Text Available Using approximation results, we characterize the existence of the solution for a two-dimensional moment problem in the first quadrant, in terms of quadratic forms, similar to the one-dimensional case. For the bounded domain case, one considers a space of complex analytic functions in a disk and a space of continuous functions on a compact interval. The latter result seems to give sufficient (and necessary conditions for the existence of a multiplicative solution.
Of Models and Machines: Implementing Bounded Rationality.
Dick, Stephanie
2015-09-01
This essay explores the early history of Herbert Simon's principle of bounded rationality in the context of his Artificial Intelligence research in the mid 1950s. It focuses in particular on how Simon and his colleagues at the RAND Corporation translated a model of human reasoning into a computer program, the Logic Theory Machine. They were motivated by a belief that computers and minds were the same kind of thing--namely, information-processing systems. The Logic Theory Machine program was a model of how people solved problems in elementary mathematical logic. However, in making this model actually run on their 1950s computer, the JOHNNIAC, Simon and his colleagues had to navigate many obstacles and material constraints quite foreign to the human experience of logic. They crafted new tools and engaged in new practices that accommodated the affordances of their machine, rather than reflecting the character of human cognition and its bounds. The essay argues that tracking this implementation effort shows that "internal" cognitive practices and "external" tools and materials are not so easily separated as they are in Simon's principle of bounded rationality--the latter often shaping the dynamics of the former. PMID:26685521
Branching and annihilating random walks: exact results at low branching rate.
Benitez, Federico; Wschebor, Nicolás
2013-05-01
We present some exact results on the behavior of branching and annihilating random walks, both in the directed percolation and parity conserving universality classes. Contrary to usual perturbation theory, we perform an expansion in the branching rate around the nontrivial pure annihilation (PA) model, whose correlation and response function we compute exactly. With this, the nonuniversal threshold value for having a phase transition in the simplest system belonging to the directed percolation universality class is found to coincide with previous nonperturbative renormalization group (RG) approximate results. We also show that the parity conserving universality class has an unexpected RG fixed point structure, with a PA fixed point which is unstable in all dimensions of physical interest. PMID:23767512
Upper and lower bounds on quantum codes
Smith, Graeme Stewart Baird
This thesis provides bounds on the performance of quantum error correcting codes when used for quantum communication and quantum key distribution. The first two chapters provide a bare-bones introduction to classical and quantum error correcting codes, respectively. The next four chapters present achievable rates for quantum codes in various scenarios. The final chapter is dedicated to an upper bound on the quantum channel capacity. Chapter 3 studies coding for adversarial noise using quantum list codes, showing there exist quantum codes with high rates and short lists. These can be used, together with a very short secret key, to communicate with high fidelity at noise levels for which perfect fidelity is, impossible. Chapter 4 explores the performance of a family of degenerate codes when used to communicate over Pauli channels, showing they can be used to communicate over almost any Pauli channel at rates that are impossible for a nondegenerate code and that exceed those of previously known degenerate codes. By studying the scaling of the optimal block length as a function of the channel's parameters, we develop a heuristic for designing even better codes. Chapter 5 describes an equivalence between a family of noisy preprocessing protocols for quantum key distribution and entanglement distillation protocols whose target state belongs to a class of private states called "twisted states." In Chapter 6, the codes of Chapter 4 are combined with the protocols of Chapter 5 to provide higher key rates for one-way quantum key distribution than were previously thought possible. Finally, Chapter 7 presents a new upper bound on the quantum channel capacity that is both additive and convex, and which can be interpreted as the capacity of the channel for communication given access to side channels from a class of zero capacity "cloning" channels. This "clone assisted capacity" is equal to the unassisted capacity for channels that are degradable, which we use to find new upper
CYANOGEN IN NGC 1851 RED GIANT BRANCH AND ASYMPTOTIC GIANT BRANCH STARS: QUADRIMODAL DISTRIBUTIONS
Energy Technology Data Exchange (ETDEWEB)
Campbell, S. W.; Stancliffe, R. J.; Lattanzio, J. C.; Angelou, G. C.; D' Orazi, V. [Monash Centre for Astrophysics, P.O. Box 28M, Victoria 3800 (Australia); Yong, D.; Wylie-de Boer, E. C. [Research School of Astronomy and Astrophysics, Australian National University, Weston, ACT 2611 (Australia); Martell, S. L. [Australian Astronomical Observatory, North Ryde, NSW 2113 (Australia); Grundahl, F. [Department of Physics and Astronomy, Aarhus University, Ny Munkegade, DK-8000 Aarhus C (Denmark); Sneden, C., E-mail: simon.campbell@monash.edu, E-mail: david.yong@anu.edu.au [Department of Astronomy and McDonald Observatory, University of Texas, Austin, TX 78712 (United States)
2012-12-10
The Galactic globular cluster NGC 1851 has raised much interest since Hubble Space Telescope photometry revealed that it hosts a double subgiant branch. Here we report on our homogeneous study into the cyanogen (CN) band strengths in the red giant branch (RGB) population (17 stars) and asymptotic giant branch (AGB) population (21 stars) using AAOmega/2dF spectra with R {approx} 3000. We discover that NGC 1851 hosts a quadrimodal distribution of CN band strengths in its RGB and AGB populations. This result supports the merger formation scenario proposed for this cluster, such that the CN quadrimodality could be explained by the superposition of two 'normal' bimodal populations. A small sample overlap with an abundance catalog allowed us to tentatively explore the relationship between our CN populations and a range of elemental abundances. We found a striking correlation between CN and [O/Na]. We also found that the four CN peaks may be paired-the two CN-weaker populations being associated with low Ba and the two CN-stronger populations with high Ba. If true, then s-process abundances would be a good diagnostic for disentangling the two original clusters in the merger scenario. More observations are needed to confirm the quadrimodality and also the relationship between the subpopulations. We also report CN results for NGC 288 as a comparison. Our relatively large samples of AGB stars show that both clusters have a bias toward CN-weak AGB populations.
Pebbling and Branching Programs Solving the Tree Evaluation Problem
Wehr, Dustin
2010-01-01
We study restricted computation models related to the Tree Evaluation Problem}. The TEP was introduced in earlier work as a simple candidate for the (*very*) long term goal of separating L and LogDCFL. The input to the problem is a rooted, balanced binary tree of height h, whose internal nodes are labeled with binary functions on [k] = {1,...,k} (each given simply as a list of k^2 elements of [k]), and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its binary function applied to the values of its children, and the output is the value of the root. The first restricted computation model, called Fractional Pebbling, is a generalization of the black/white pebbling game on graphs, and arises in a natural way from the search for good upper bounds on the size of nondeterministic branching programs (BPs) solving the TEP - for any fixed h, if the binary tree of height h has fractional pebbling cost at most p, then there are nondeterministic BPs of size O(k^p) solving the heigh...
Aggregation Dynamics Using Phase Wave Signals and Branching Patterns
Sakaguchi, Hidetsugu; Kusagaki, Takuma
2016-09-01
The aggregation dynamics of slime mold is studied using coupled equations of phase ϕ and cell concentration n. Phase waves work as tactic signals for aggregation. Branching structures appear during the aggregation. A stationary branching pattern appears like a river network, if cells are uniformly supplied into the system.
Branched nanostructures and method of synthesizing the same
Fonseca, Luis F. (Inventor); Resto, Oscar (Inventor); Sola, Francisco (Inventor)
2009-01-01
A branched nanostructure is synthesized. A porous material, with pores having a diameter of approximately 1 .mu.m or less, is placed in a vacuum. It is irradiated with an electron beam. This causes a trunk to grow from the porous material and further causes branches to grow from the trunk.
Jiang, Yonghong; Sun, Weiguo; Zhang, Yi; Fu, Jia; Fan, Qunchao; Li, Huidong; Feng, Hao
2016-06-01
The difference converging method (DCM) used to predict the R-branch and the Q-branch high-lying rotational lines for diatomic systems is improved in this study. The key analytical formulae of the DCM method are modified by adding a higher order spectral term Hυ, and adding a physical converging criterion to improve the accuracy of predictions. Applications of the improved DCM method to the R-branch of the TiF molecule and the Q-branch of the 193IrN molecule show that the accuracy of the R-branch and the Q-branch rotational lines is about one order of magnitude better than the results obtained using the previous formulae, which demonstrate the necessity of the added small term Hυ and the physical converging criterion. The DCM results are also shown to be better than the extrapolated rotational lines using the least-squares method.
Jiang, Yonghong; Sun, Weiguo; Zhang, Yi; Fu, Jia; Fan, Qunchao; Li, Huidong; Feng, Hao
2016-06-01
The difference converging method (DCM) used to predict the R-branch and the Q-branch high-lying rotational lines for diatomic systems is improved in this study. The key analytical formulae of the DCM method are modified by adding a higher order spectral term Hυ, and adding a physical converging criterion to improve the accuracy of predictions. Applications of the improved DCM method to the R-branch of the TiF molecule and the Q-branch of the (193)IrN molecule show that the accuracy of the R-branch and the Q-branch rotational lines is about one order of magnitude better than the results obtained using the previous formulae, which demonstrate the necessity of the added small term Hυ and the physical converging criterion. The DCM results are also shown to be better than the extrapolated rotational lines using the least-squares method. PMID:26974473
Linear and Branched PEIs (Polyethylenimines) and Their Property Space
Lungu, Claudiu N.; Diudea, Mircea V.; Putz, Mihai V.; Grudziński, Ireneusz P.
2016-01-01
A chemical property space defines the adaptability of a molecule to changing conditions and its interaction with other molecular systems determining a pharmacological response. Within a congeneric molecular series (compounds with the same derivatization algorithm and thus the same brute formula) the chemical properties vary in a monotonic manner, i.e., congeneric compounds share the same chemical property space. The chemical property space is a key component in molecular design, where some building blocks are functionalized, i.e., derivatized, and eventually self-assembled in more complex systems, such as enzyme-ligand systems, of which (physico-chemical) properties/bioactivity may be predicted by QSPR/QSAR (quantitative structure-property/activity relationship) studies. The system structure is determined by the binding type (temporal/permanent; electrostatic/covalent) and is reflected in its local electronic (and/or magnetic) properties. Such nano-systems play the role of molecular devices, important in nano-medicine. In the present article, the behavior of polyethylenimine (PEI) macromolecules (linear LPEI and branched BPEI, respectively) with respect to the glucose oxidase enzyme GOx is described in terms of their (interacting) energy, geometry and topology, in an attempt to find the best shape and size of PEIs to be useful for a chosen (nanochemistry) purpose. PMID:27089324
Bounded rationality and heterogeneous expectations in macroeconomics
D. Massaro
2012-01-01
This thesis studies the effect of individual bounded rationality on aggregate macroeconomic dynamics. Boundedly rational agents are specified as using simple heuristics in their decision making. An important aspect of the type of bounded rationality described in this thesis is that the population of
3-hitting set on Bounded Degree Hypergraphs: Upper and Lower Bounds on the Kernel Size
Kanj, Iyad A.; Zhang, Fenghui
We study upper and lower bounds on the kernel size for the 3-hitting set problem on hypergraphs of degree at most 3, denoted 3-3-hs. We first show that, unless P=NP, 3-3-hs on 3-uniform hypergraphs does not have a kernel of size at most 35k/19 > 1.8421k. We then give a 4k - k 0.2692 kernel for 3-3-hs that is computable in time O(k 1.2692). This result improves the upper bound of 4k on the kernel size for 3-3-hs, given by Wahlström. We also show that the upper bound results on the kernel size for 3-3-hs can be generalized to the 3-hs problem on hypergraphs of bounded degree Δ, for any integer-constant Δ> 3.
Valuation models and Simon's bounded rationality
Directory of Open Access Journals (Sweden)
Alexandra Strommer de Farias Godoi
2009-09-01
Full Text Available This paper aims at reconciling the evidence that sophisticated valuation models are increasingly used by companies in their investment appraisal with the literature of bounded rationality, according to which objective optimization is impracticable in the real world because it would demand an immense level of sophistication of the analytical and computational processes of human beings. We show how normative valuation models should rather be viewed as forms of reality representation, frameworks according to which the real world is perceived, fragmented for a better understanding, and recomposed, providing an orderly method for undertaking a task as complex as the investment decision.
Business Systems Branch Abilities, Capabilities, and Services Web Page
Cortes-Pena, Aida Yoguely
2009-01-01
During the INSPIRE summer internship I acted as the Business Systems Branch Capability Owner for the Kennedy Web-based Initiative for Communicating Capabilities System (KWICC), with the responsibility of creating a portal that describes the services provided by this Branch. This project will help others achieve a clear view ofthe services that the Business System Branch provides to NASA and the Kennedy Space Center. After collecting the data through the interviews with subject matter experts and the literature in Business World and other web sites I identified discrepancies, made the necessary corrections to the sites and placed the information from the report into the KWICC web page.
Kim, Jeong Han; Montenegro, Ravi; Peres, Yuval; Tetali, Prasad
2010-01-01
We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group $G$ and find that if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in $\\Theta(\\sqrt{|G|})$ steps. Moreover, for the parallelized distinguished points algorithm on $J$ processors we find that $\\Theta(\\sqrt{|G|}/J)$ steps suffi...
Model-Independent Analysis of B -> pi K Decays and Bounds on the Weak Phase gamma
Neubert, Matthias(PRISMA Cluster of Excellence & Mainz Institut for Theoretical Physics, Johannes Gutenberg University, D-55099, Mainz, Germany)
1998-01-01
A general parametrization of the amplitudes for the rare two-body decays B -> pi K is introduced, which makes maximal use of theoretical constraints arising from flavour symmetries of the strong interactions and the structure of the low-energy effective weak Hamiltonian. With the help of this parametrization, a model-independent analysis of the branching ratios and direct CP asymmetries in the various B -> pi K decay modes is performed, and the impact of hadronic uncertainties on bounds on th...
Systematic vs. Non-systematic Algorithms for Solving the MPE Task
Marinescu, Radu; Kask, Kalev; Dechter, Rina
2012-01-01
The paper continues the study of partitioning based inference of heuristics for search in the context of solving the Most Probable Explanation task in Bayesian Networks. We compare two systematic Branch and Bound search algorithms, BBBT (for which the heuristic information is constructed during search and allows dynamic variable/value ordering) and its predecessor BBMB (for which the heuristic information is pre-compiled), against a number of popular local search algorithms for the MPE proble...
Czech Academy of Sciences Publication Activity Database
Ebenlendr, Tomáš; Sgall, J.
2015-01-01
Roč. 56, č. 1 (2015), s. 73-81. ISSN 1432-4350 R&D Projects: GA ČR GBP202/12/G061; GA AV ČR IAA100190902 Institutional support: RVO:67985840 Keywords : online algorithms * scheduling * makespan Subject RIV: BA - General Mathematics Impact factor: 0.533, year: 2014 http://link.springer.com/article/10.1007%2Fs00224-013-9451-6
Institute of Scientific and Technical Information of China (English)
李树刚; 吴智铭; 庞小红
2004-01-01
In order to study the capacitated lot sizing problem for a supply chain of corporate multi-location fac-tories to minimize the total costs of production, inventory and transportation under the system capacity restriction and product due date, while at the same time considering the menu distributed balance, the mathematical pro-gramming models are decomposed and reduced from the 3 levels into 2 levels according to the idea of just-in-time production. In order to overcome the premature convergence of ACA (ant colony algorithms) , the idea of mute operation is adopted in genetic algorithms and a PACA (parallel ant colony algorithms) is proposed forsupply chain optimization. Finally, an illustrative example is given, and a comparison is made with standard BAR ( Branch and Bound) and PACA approach. The result shows that the latter is more effective and promis-ing.
Improved Bounds for Beacon-Based Coverage and Routing in Simple Rectilinear Polygons
Bae, Sang Won; Shin, Chan-Su; Vigneron, Antoine
2015-01-01
We establish tight bounds for beacon-based coverage problems, and improve the bounds for beacon-based routing problems in simple rectilinear polygons. Specifically, we show that $\\lfloor \\frac{n}{6} \\rfloor$ beacons are always sufficient and sometimes necessary to cover a simple rectilinear polygon $P$ with $n$ vertices. We also prove tight bounds for the case where $P$ is monotone, and we present an optimal linear-time algorithm that computes the beacon-based kernel of $P$. For the routing p...
THE UPTAKE OF AROMATIC AND BRANCHED CHAIN HYDROCARBONS BY YEAST
Studies of the hydrocarbon utilizing yeasts, Candida maltosa and C. lipolytica, have shown that both were capable of reducing recoverable amounts of branched chain and aromatic hydrocarbons in a mixture of naphthalene, tetradecane, hexadecane, pristane (tetra-methylpentadecane). ...
Semiparametric bounds of mean and variance for exotic options
Institute of Scientific and Technical Information of China (English)
2009-01-01
Finding semiparametric bounds for option prices is a widely studied pricing technique.We obtain closed-form semiparametric bounds of the mean and variance for the pay-off of two exotic(Collar and Gap) call options given mean and variance information on the underlying asset price.Mathematically,we extended domination technique by quadratic functions to bound mean and variances.
Semiparametric bounds of mean and variance for exotic options
Institute of Scientific and Technical Information of China (English)
LIU GuoQing; LI V.Wenbo
2009-01-01
Finding semiparametric bounds for option prices is a widely studied pricing technique. We obtain closed-form semiparametric bounds of the mean and variance for the pay-off of two exotic (Collar and Gap) call options given mean and variance information on the underlying asset price. Mathematically, we extended domination technique by quadratic functions to bound mean and variances.
Regret Bounds for Deterministic Gaussian Process Bandits
de Freitas, Nando; Zoghi, Masrour
2012-01-01
This paper analyses the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al., 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, (Srinivas et al., 2010) proved that the regret vanishes at the approximate rate of $O(\\frac{1}{\\sqrt{t}})$, where t is the number of observations. To complement their result, we attack the deterministic case and attain a much faster exponential convergence rate. Under some regularity assumptions, we show that the regret decreases asymptotically according to $O(e^{-\\frac{\\tau t}{(\\ln t)^{d/4}}})$ with high probability. Here, d is the dimension of the search space and $\\tau$ is a constant that depends on the behaviour of the objective function near its global maximum.
Design and Performance Evaluation of Sequence Partition Algorithms
Institute of Scientific and Technical Information of China (English)
Bing Yang; Jing Chen; En-Yue Lu; Si-Qing Zheng
2008-01-01
Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone (increasing or decreasing) case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O(n3), a known greedy algorithm of time complexity O(n1.5 log n), and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.
Size-exclusion chromatography (SEC) of branched polymers and polysaccharides
Gaborieau, Marianne; Castignolles, Patrice
2010-01-01
Branched polymers are among the most important polymers, ranging from polyolefins to polysaccharides. Branching plays a key role in the chain dynamics. It is thus very important for application properties such as mechanical and adhesive properties and digestibility. It also plays a key role in viscous properties, and thus in the mechanism of the separation of these polymers in size-exclusion chromatography (SEC). Critically reviewing the literature, particularly on SEC of polyolefins, polyacr...
Manifolds with minimal horospheres and bounded derivative stability vector fields
International Nuclear Information System (INIS)
Let (M,g) be a geodesically complete and an infinite volume Riemannian manifold with minimal horospheres and bounded derivative stability vector field. We prove that bounded functions on M having the mean-value property are constant. We extend thus a result of the authors, where they proved a similar result for bounded harmonic functions on harmonic manifolds with minimal horospheres. (author)
Consumer choice and revealed bounded rationality
Manzini, Paola; Mariotti, Marco
2006-01-01
We study two boundedly rational procedures in consumer behavior. We show that these procedures can be detected by conditions on observable demand data of the same type as standard revealed preference axioms. This provides the basis for a non-parametric analysis of boundedly rational consumer behavior mirroring the classical one for utility maximization.
Polynomially Bounded Sequences and Polynomial Sequences
Directory of Open Access Journals (Sweden)
Okazaki Hiroyuki
2015-09-01
Full Text Available In this article, we formalize polynomially bounded sequences that plays an important role in computational complexity theory. Class P is a fundamental computational complexity class that contains all polynomial-time decision problems [11], [12]. It takes polynomially bounded amount of computation time to solve polynomial-time decision problems by the deterministic Turing machine. Moreover we formalize polynomial sequences [5].
Bounded Rationality, Retaliation, and the Spread of Urban Violence
Jacobs, Bruce A.; Wright, Richard
2010-01-01
Drawing from in-depth interviews with 52 active street criminals, this article examines the grounded theoretic implications of bounded rationality for retaliatory street violence. The bounds on rationality that this article explores are anger, uncertainty, and time pressure. These bounds create imperfections in the retaliatory decision-making…
F-Theory, spinning black holes and multi-string branches
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.
Decoherence and the Branching of Chaos-less Classical Trajectory
Ishikawa, Takuji
2016-01-01
This study was started to know mysterious classicality of nuclei. This time, I found a new rule for decoherence. I used a model without chaos. As a result, it was shown that not only the intersection of classical trajectories but also branching of classical trajectories are needed for decoherence. In other words, it was shown that interactions between a main system and environments have to make enough branchings of classical trajectories of the main system for decoherence.
DEFF Research Database (Denmark)
Shaik, Shahnoor S.; Obata, Toshihiro; Hebelstrup, Kim H;
2016-01-01
-structure was achieved by decreasing starch branching and increasing starch-bound phosphate content in the barley caryopsis starch by RNAi suppression of all three Starch Branching Enzyme (SBE) isoforms or overexpression of potato Glucan Water Dikinase (GWD). The resulting lines displayed Amylose-Only (AO) and Hyper...... high levels of some important stress-related metabolites and potentially protective metabolites, possibly to elude deleterious effects. Investigations on starch molecular structure revealed significant increase in starch phosphate and amylose content in HP and AO respectively with obvious differences...
F-Theory, Spinning Black Holes and Multi-string Branches
Haghighat, Babak; Vafa, Cumrun; Vandoren, Stefan
2015-01-01
We study 5d supersymmetric black holes which descend from strings of generic $\\mathcal{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 l...
Remote Procedures Calls Implementing using Distributed Algorithm
Directory of Open Access Journals (Sweden)
G. MURALI
2011-11-01
Full Text Available Remote Procedure Call (RPC is a powerful primitive used for communication and synchronization between distributed processes. RPC poses a problem that it reduces the amount of parallelism, because of its synchronous nature. This paper shows how simple processes can be used to find a way of avoiding a difficulty in this problem. The combination of blocking RPC calls and light-weightprocesses provides both simple semantics and efficient exploitation of parallelism.We will describe how two important classes of algorithms, branch and bound can be run in a parallel way using this RPC. The results of some experiments comparing this algorithms on a single processor discussed
Do Reuss and Voigt Bounds Really Bound in High-Pressure Rheology Experiments?
Energy Technology Data Exchange (ETDEWEB)
Chen,J.; Li, L.; Yu, T.; Long, H.; Weidner, D.; Wang, L.; Vaughan, M.
2006-01-01
Energy dispersive synchrotron x-ray diffraction is carried out to measure differential lattice strains in polycrystalline Fe{sub 2}SiO{sub 4} (fayalite) and MgO samples using a multi-element solid state detector during high-pressure deformation. The theory of elastic modeling with Reuss (iso-stress) and Voigt (iso-strain) bounds is used to evaluate the aggregate stress and weight parameter, {alpha} (0{le}{alpha}{le}1), of the two bounds. Results under the elastic assumption quantitatively demonstrate that a highly stressed sample in high-pressure experiments reasonably approximates to an iso-stress state. However, when the sample is plastically deformed, the Reuss and Voigt bounds are no longer valid ({alpha} becomes beyond 1). Instead, if plastic slip systems of the sample are known (e.g. in the case of MgO), the aggregate property can be modeled using a visco-plastic self-consistent theory.
Do Reuss and Voigt bounds really bound in high-pressure rheology experiments?
Energy Technology Data Exchange (ETDEWEB)
Chen Jiuhua; Li Li; Yu, Tony; Long Hongbo; Weidner, Donald; Wang Liping; Vaughan, Michael [Mineral Physics Institute and Department of Geosciences, Stony Brook University, Stony Brook, NY 11794-2100 (United States)
2006-06-28
Energy dispersive synchrotron x-ray diffraction is carried out to measure differential lattice strains in polycrystalline Fe{sub 2}SiO{sub 4} (fayalite) and MgO samples using a multi-element solid state detector during high-pressure deformation. The theory of elastic modelling with Reuss (iso-stress) and Voigt (iso-strain) bounds is used to evaluate the aggregate stress and weight parameter, {alpha} (0{<=}{alpha}{<=}1), of the two bounds. Results under the elastic assumption quantitatively demonstrate that a highly stressed sample in high-pressure experiments reasonably approximates to an iso-stress state. However, when the sample is plastically deformed, the Reuss and Voigt bounds are no longer valid ({alpha} becomes beyond 1). Instead, if plastic slip systems of the sample are known (e.g. in the case of MgO), the aggregate property can be modelled using a visco-plastic self-consistent theory.
Do Reuss and Voigt bounds really bound in high-pressure rheology experiments?
Chen, Jiuhua; Li, Li; Yu, Tony; Long, Hongbo; Weidner, Donald; Wang, Liping; Vaughan, Michael
2006-06-28
Energy dispersive synchrotron x-ray diffraction is carried out to measure differential lattice strains in polycrystalline Fe(2)SiO(4) (fayalite) and MgO samples using a multi-element solid state detector during high-pressure deformation. The theory of elastic modelling with Reuss (iso-stress) and Voigt (iso-strain) bounds is used to evaluate the aggregate stress and weight parameter, α (0≤α≤1), of the two bounds. Results under the elastic assumption quantitatively demonstrate that a highly stressed sample in high-pressure experiments reasonably approximates to an iso-stress state. However, when the sample is plastically deformed, the Reuss and Voigt bounds are no longer valid (α becomes beyond 1). Instead, if plastic slip systems of the sample are known (e.g. in the case of MgO), the aggregate property can be modelled using a visco-plastic self-consistent theory. PMID:22611095
International Nuclear Information System (INIS)
It is anticipated that the new SRS NPDES permit will require toxicity testing of at numerous outfalls and receiving streams, using the standard test species, Ceriodaphnia dubia. Because SRS surface waters differ markedly from the standard culture water that is used for Ceriodaphnia, studies were undertaken to determine if unimpacted SRS surface waters will support this species. Three SRS surface waters were evaluated; Upper Three Runs at Road 8-1, Pen Branch at Road B, and Fourmile Branch at Road F. Toxicity tests were performed monthly on each water source for eleven months. All three water sources exhibited varying degrees of toxicity to Ceriodaphnia, with Pen Branch being the least toxic and Fourmile Branch being the most toxic. These results indicate that if in-stream toxicity testing is required, it may not be possible to separate the naturally occurring toxic effects of the receiving water from possible toxic effects of SRS effluents
Directory of Open Access Journals (Sweden)
Daniela J. López-Araujo
2013-01-01
Full Text Available In this work, an output‐feedback adaptive SP‐SD‐type control scheme for the global position stabilization of robot manipulators with bounded inputs is proposed. Compared with the output‐feedback adaptive approaches previously developed in a bounded‐ input context, the proposed velocity‐free feedback controller guarantees the adaptive regulation objective globally (i.e. for any initial condition, avoiding discontinuities throughout the scheme, preventing the inputs from reaching their natural saturation bounds and imposing no saturation-avoidance restrictions on the choice of the P and D control gains. Moreover, through its extended structure, the adaptation algorithm may be configured to evolve either in parallel (independently or interconnected to the velocity estimation (motion dissipation auxiliary dynamics, giving an additional degree of design flexibility. Furthermore, the proposed scheme is not restricted to the use of a specific saturation function to achieve the required boundedness, but may involve any one within a set of smooth and non‐smooth (Lipschitz‐continuous bounded passive functions that include the hyperbolic tangent and the conventional saturation as particular cases. Experimental results on a 3‐ degree‐of‐freedom manipulator corroborate the efficiency of the proposed scheme.
Lower and Upper Bounds for Deniable Public-Key Encryption
DEFF Research Database (Denmark)
Bendlin, Rikke; Nielsen, Jesper Buus; Nordholt, Peter Sebastian;
2011-01-01
impossible to construct a non-interactive bi-deniable public-key encryption scheme with better than polynomial security. Specifically, we give an explicit bound relating the security of the scheme to how efficient the scheme is in terms of key size. Our impossibility result establishes a lower bound on the...... security. As a final contribution we give constructions of deniable public-key encryption schemes which establishes upper bounds on the security in terms of key length. There is a gap between our lower and upper bounds, which leaves the interesting open problem of finding the tight bounds....
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
Randomized algorithms for matrices and data
Mahoney, Michael W
2011-01-01
Randomized algorithms for very large matrix problems have received a great deal of attention in recent years. Much of this work was motivated by problems in large-scale data analysis. Although this work had its origins within theoretical computer science, where researchers were interested in proving worst-case bounds, i.e., bounds without any assumptions at all on the input data, researchers from numerical linear algebra, statistics, applied mathematics, data analysis, and machine learning, as well as domain scientists have subsequently extended and applied these methods in important ways. Although this has been great for the development of the area and for the technology transfer of theoretical ideas into practical applications, this interdisciplinarity has thus far sometimes obscured the underlying simplicity and generality of the core ideas. This review will provide a detailed overview of recent work on randomized algorithms for matrix problems, with an emphasis on a few simple core ideas that underlie not...
Kortstee, A.J.
1997-01-01
Starch consists of two major components; amylose and amylopectin. Amylose is synthesized by the enzyme Granule-Bound Starch Syntase (GBSS) and consists of essentially linear chains of α-1,4 linked glucose residues. Amylopectin is synthesized by the combined activity of the enzymes Soluble Starch Synthase (SSS) and Branching enzyme (BE) and consists of linear α-1,4 linked glucosidic chains with α-1,6 linked branchpoints. The amount and fine structure of each of the components determine the sta...
Adaptive path planning: Algorithm and analysis
Energy Technology Data Exchange (ETDEWEB)
Chen, Pang C.
1995-03-01
To address the need for a fast path planner, we present a learning algorithm that improves path planning by using past experience to enhance future performance. The algorithm relies on an existing path planner to provide solutions difficult tasks. From these solutions, an evolving sparse work of useful robot configurations is learned to support faster planning. More generally, the algorithm provides a framework in which a slow but effective planner may be improved both cost-wise and capability-wise by a faster but less effective planner coupled with experience. We analyze algorithm by formalizing the concept of improvability and deriving conditions under which a planner can be improved within the framework. The analysis is based on two stochastic models, one pessimistic (on task complexity), the other randomized (on experience utility). Using these models, we derive quantitative bounds to predict the learning behavior. We use these estimation tools to characterize the situations in which the algorithm is useful and to provide bounds on the training time. In particular, we show how to predict the maximum achievable speedup. Additionally, our analysis techniques are elementary and should be useful for studying other types of probabilistic learning as well.
Comparison Study for Clonal Selection Algorithm and Genetic Algorithm
Ezgi Deniz Ulker; Sadık Ulker
2012-01-01
Two metaheuristic algorithms namely Artificial Immune Systems (AIS) and Genetic Algorithms are classified as computational systems inspired by theoretical immunology and genetics mechanisms. In this work we examine the comparative performances of two algorithms. A special selection algorithm, Clonal Selection Algorithm (CLONALG), which is a subset of Artificial Immune Systems, and Genetic Algorithms are tested with certain benchmark functions. It is shown that depending on type of a function ...
Parallel Algorithms and Patterns
Energy Technology Data Exchange (ETDEWEB)
Robey, Robert W. [Los Alamos National Lab. (LANL), Los Alamos, NM (United States)
2016-06-16
This is a powerpoint presentation on parallel algorithms and patterns. A parallel algorithm is a well-defined, step-by-step computational procedure that emphasizes concurrency to solve a problem. Examples of problems include: Sorting, searching, optimization, matrix operations. A parallel pattern is a computational step in a sequence of independent, potentially concurrent operations that occurs in diverse scenarios with some frequency. Examples are: Reductions, prefix scans, ghost cell updates. We only touch on parallel patterns in this presentation. It really deserves its own detailed discussion which Gabe Rockefeller would like to develop.
FY 1991 Measurements and Characterization Branch annual report
Energy Technology Data Exchange (ETDEWEB)
Osterwald, C.R.; Dippo, P.C. [eds.
1992-11-01
The Measurements and Characterization Branch of the National Renewable Laboratory (NREL) provides comprehensive photovoltaic (PV) materials, devices, characterization, measurement, fabrication, modeling research, and support for the international PV research community, in the context of the US Department of Energy`s Photovoltaic Research Program goals. This report summarizes the progress of the Branch from 31 January 1991 through 31 January 1992. The eight technical sections present a succinct overview of the capabilities and accomplishments of each group in the Branch. The Branch is comprised of the following groups: Surface and interface Analysis; Materials Characterization; Device Development; Electro-optical Characterization; Advanced PV module Performance and Reliability Research; Cell Performance Characterization; Surface Interactions, Modification, and Stability; and FTIR Spectroscopic Research. The including measurements and tests of PV materials, cells, submodules, and modules. The report contains a comprehensive bibliography of 77 branch originated journal and conference publications, which were authored in collaboration with, or in support of, approximately 135 university, industrial, government, and in-house research groups.
FY 1991 Measurements and Characterization Branch annual report
Energy Technology Data Exchange (ETDEWEB)
Osterwald, C.R.; Dippo, P.C. (eds.)
1992-11-01
The Measurements and Characterization Branch of the National Renewable Laboratory (NREL) provides comprehensive photovoltaic (PV) materials, devices, characterization, measurement, fabrication, modeling research, and support for the international PV research community, in the context of the US Department of Energy's Photovoltaic Research Program goals. This report summarizes the progress of the Branch from 31 January 1991 through 31 January 1992. The eight technical sections present a succinct overview of the capabilities and accomplishments of each group in the Branch. The Branch is comprised of the following groups: Surface and interface Analysis; Materials Characterization; Device Development; Electro-optical Characterization; Advanced PV module Performance and Reliability Research; Cell Performance Characterization; Surface Interactions, Modification, and Stability; and FTIR Spectroscopic Research. The including measurements and tests of PV materials, cells, submodules, and modules. The report contains a comprehensive bibliography of 77 branch originated journal and conference publications, which were authored in collaboration with, or in support of, approximately 135 university, industrial, government, and in-house research groups.
Thulasiraman, K
2011-01-01
This adaptation of an earlier work by the authors is a graduate text and professional reference on the fundamentals of graph theory. It covers the theory of graphs, its applications to computer networks and the theory of graph algorithms. Also includes exercises and an updated bibliography.
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...
Dippel, O.; Brandl, V.; Bässler, H.; Danieli, R.; Zamboni, R.; Taliani, C.
1993-12-01
The fluorescence yield of thin films of sexithienyl drops rapidly above the S 1←S 0 absorption edge while the yield of photocarrier generation increases simultaneously. This unusual behavior of a molecular solid is interpreted in terms of an energy-dependent branching between fluorescence and dissociation of a singlet excitation into a weakly bound electron—hole pair. This is shown to be a characteristic feature of a disordered system in which the energy levels of both neutral and charged excitations are subject to inhomogeneous broadening. In T6 the latter arises from torsional displacement of the thienylene moities.
Okamoto, Norio; Matsumoto, Chota; Shimomura, Yoshikazu
2014-01-01
Background There are some cases that reported central retinal vein occlusion accompanied by ciliary artery occlusion, however, combined branch retinal artery and vein occlusion is a rare condition that has been infrequently reported. We describe in this report one case of retinal vein occlusion and branch retinal artery occlusion occurring simultaneously. Case presentation A 50 year-old woman presented with acute visual loss in her right eye. Fundus photography showed retinal ischemia and tor...
Size-exclusion chromatography (SEC) of branched polymers and polysaccharides.
Gaborieau, Marianne; Castignolles, Patrice
2011-02-01
Branched polymers are among the most important polymers, ranging from polyolefins to polysaccharides. Branching plays a key role in the chain dynamics. It is thus very important for application properties such as mechanical and adhesive properties and digestibility. It also plays a key role in viscous properties, and thus in the mechanism of the separation of these polymers in size-exclusion chromatography (SEC). Critically reviewing the literature, particularly on SEC of polyolefins, polyacrylates and starch, we discuss common pitfalls but also highlight some unexplored possibilities to characterize branched polymers. The presence of a few long-chain branches has been shown to lead to a poor separation in SEC, as evidenced by multiple-detection SEC or multidimensional liquid chromatography. The local dispersity can be large in that case, and the accuracy of molecular weight determination achieved by current methods is poor, although hydrodynamic volume distributions offer alternatives. In contrast, highly branched polymers do not suffer from this extensive incomplete separation in terms of molecular weight. PMID:20967430
Path integral formulation and Feynman rules for phylogenetic branching models
International Nuclear Information System (INIS)
A dynamical picture of phylogenetic evolution is given in terms of Markov models on a state space, comprising joint probability distributions for character types of taxonomic classes. Phylogenetic branching is a process which augments the number of taxa under consideration, and hence the rank of the underlying joint probability state tensor. We point out the combinatorial necessity for a second-quantized, or Fock space setting, incorporating discrete counting labels for taxa and character types, to allow for a description in the number basis. Rate operators describing both time evolution without branching, and also phylogenetic branching events, are identified. A detailed development of these ideas is given, using standard transcriptions from the microscopic formulation of non-equilibrium reaction-diffusion or birth-death processes. These give the relations between stochastic rate matrices, the matrix elements of the corresponding evolution operators representing them, and the integral kernels needed to implement these as path integrals. The 'free' theory (without branching) is solved, and the correct trilinear 'interaction' terms (representing branching events) are presented. The full model is developed in perturbation theory via the derivation of explicit Feynman rules which establish that the probabilities (pattern frequencies of leaf colourations) arising as matrix elements of the time evolution operator are identical with those computed via the standard analysis. Simple examples (phylogenetic trees with two or three leaves), are discussed in detail. Further implications for the work are briefly considered including the role of time reparametrization covariance
Flow-induced pruning of branched systems and brittle reconfiguration
Lopez, Diego; de Langre, Emmanuel
2011-01-01
Whereas most plants are flexible structures that undergo large deformations under flow, another process can occur when the plant is broken by heavy fluid-loading. We investigate here the mechanism of such possible breakage, focusing on the flow-induced pruning that can be observed in plants or aquatic vegetation when parts of the structure break under flow. By computation on an actual tree geometry, a 20-yr-old walnut tree (Juglans Regia L.) and comparison with simple models, we analyze the influence of geometrical and physical parameters on the occurrence of branch breakage and on the successive breaking events occurring in a tree-like structure when the flow velocity is increased. We show that both the branching pattern and the slenderness exponent, defining the branch taper, play a major role in the breakage scenario. We identify a criterion for branch breakage to occur before breakage of the trunk. In that case, we show that the successive breakage of peripheral branches allows the plant to sustain higher...
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; Pisinger, David
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....
Real weights, bound states and duality orbits
Marrani, Alessio; Romano, Luca
2015-01-01
We show that the duality orbits of extremal black holes in supergravity theories with symmetric scalar manifolds can be derived by studying the stabilizing subalgebras of suitable representatives, realized as bound states of specific weight vectors of the corresponding representation of the duality symmetry group. The weight vectors always correspond to weights that are real, where the reality properties are derived from the Tits-Satake diagram that identifies the real form of the Lie algebra of the duality symmetry group. Both N=2 magic Maxwell-Einstein supergravities and the semisimple infinite sequences of N=2 and N=4 theories in D=4 and 5 are considered, and various results, obtained over the years in the literature using different methods, are retrieved. In particular, we show that the stratification of the orbits of these theories occurs because of very specific properties of the representations: in the case of the theory based on the real numbers, whose symmetry group is maximally non-compact and there...
Real weights, bound states and duality orbits
Marrani, Alessio; Riccioni, Fabio; Romano, Luca
2016-01-01
We show that the duality orbits of extremal black holes in supergravity theories with symmetric scalar manifolds can be derived by studying the stabilizing subalgebras of suitable representatives, realized as bound states of specific weight vectors of the corresponding representation of the duality symmetry group. The weight vectors always correspond to weights that are real, where the reality properties are derived from the Tits-Satake diagram that identifies the real form of the Lie algebra of the duality symmetry group. Both 𝒩 = 2 magic Maxwell-Einstein supergravities and the semisimple infinite sequences of 𝒩 = 2 and 𝒩 = 4 theories in D = 4 and 5 are considered, and various results, obtained over the years in the literature using different methods, are retrieved. In particular, we show that the stratification of the orbits of these theories occurs because of very specific properties of the representations: in the case of the theory based on the real numbers, whose symmetry group is maximally noncompact and therefore all the weights are real, the stratification is due to the presence of weights of different lengths, while in the other cases it is due to the presence of complex weights.
Quantum CPU and Quantum Algorithm
Wang, An Min
1999-01-01
Making use of an universal quantum network -- QCPU proposed by me\\upcite{My1}, it is obtained that the whole quantum network which can implement some the known quantum algorithms including Deutsch algorithm, quantum Fourier transformation, Shor's algorithm and Grover's algorithm.
Bound states and Lorentz-Poincare symmetry
International Nuclear Information System (INIS)
A hypothesis of the ''relation-continuum'' C is put forward, closely connected with isolation of physical system, which extends to finite universal constant c the absolute nature of the Galilean relative coordinates and the absolute Newtonian time. Points of C4 continuum are directly unobservable and the relativistic symmetry L4 of directly observable space-time events becomes the limiting case of the C4-symmetry. Consequently, though the possibility of the hypothesis of C4-continuum is due to quantum physics, the modifications it implies come with finite universal constant (h/2π)/c and concern the description of the internal structure of bound states only. The C4-symmetry of relations, as weaker than the Lorentz-Poincare L4-symmetry of events, makes ''more room'' for quantum dynamical models. The Feynman graphs phenomenology with form factors (vertex functions) of non-point particles left for experimental determination can be connected with the C4-framework which determines their analytic structure. The C4-effects then would reveal themselves only in these processes in which composite particles participate. Therefore, the ''good'' quantum electrodynamics of point-particles is left unmodified. Two off-mass-shell effects are analyzed in the relatively low-energy processes which are connected with the mass-dependent localization of the center-of-mass of composite particle ''M''. They seem to be crucial for the hypothesis itself. (author)
Interactions between auxin and strigolactone in shoot branching control.
Hayward, Alice; Stirnberg, Petra; Beveridge, Christine; Leyser, Ottoline
2009-09-01
In Arabidopsis (Arabidopsis thaliana), the carotenoid cleavage dioxygenases MORE AXILLARY GROWTH3 (MAX3) and MAX4 act together with MAX1 to produce a strigolactone signaling molecule required for the inhibition of axillary bud outgrowth. We show that both MAX3 and MAX4 transcripts are positively auxin regulated in a manner similar to the orthologous genes from pea (Pisum sativum) and rice (Oryza sativa), supporting evolutionary conservation of this regulation in plants. This regulation is important for branching control because large auxin-related reductions in these transcripts are associated with increased axillary branching. Both transcripts are up-regulated in max mutants, and consistent with max mutants having increased auxin in the polar auxin transport stream, this feedback regulation involves auxin signaling. We suggest that both auxin and strigolactone have the capacity to modulate each other's levels and distribution in a dynamic feedback loop required for the coordinated control of axillary branching. PMID:19641034
He Songnian; Liang Xiao-Lan
2010-01-01
Let be a real Hilbert space and let be a boundedly Lipschitzian and strongly monotone operator. We design three hybrid steepest descent algorithms for solving variational inequality of finding a point such that , for all , where is the set of fixed points of a strict pseudocontraction, or the set of common fixed points of finite strict pseudocontractions. Strong convergence of the algorithms is proved.
Spin and relativistic motion of bound states
JÃ€rvinen, Matti
2007-01-01
The wave functions of moving bound states may be expected to contract in the direction of motion, in analogy to a rigid rod in classical special relativity, when the constituents are at equal (ordinary) time. Indeed, the Lorentz contraction of wave functions is often appealed to in qualitative discussions. However, only few field theory studies exist of equal-time wave functions in motion. In this thesis I use the Bethe-Salpeter formalism to study the wave function of a weakly bound state suc...
RADIONUCLIDE INVENTORY AND DISTRIBUTION: FOURMILE BRANCH, PEN BRANCH, AND STEEL CREEK IOUS
Energy Technology Data Exchange (ETDEWEB)
Hiergesell, R.; Phifer, M.
2014-04-29
As a condition to the Department of Energy (DOE) Low Level Waste Disposal Federal Facility Review Group (LFRG) review team approving the Savannah River Site (SRS) Composite Analysis (CA), SRS agreed to follow up on a secondary issue, which consisted of the consolidation of several observations that the team concluded, when evaluated collectively, could potentially impact the integration of the CA results. This report addresses secondary issue observations 4 and 21, which identify the need to improve the CA sensitivity and uncertainty analysis specifically by improving the CA inventory and the estimate of its uncertainty. The purpose of the work described herein was to be responsive to these secondary issue observations by re-examining the radionuclide inventories of the Integrator Operable Units (IOUs), as documented in ERD 2001 and Hiergesell, et. al. 2008. The LFRG concern has been partially addressed already for the Lower Three Runs (LTR) IOU (Hiergesell and Phifer, 2012). The work described in this investigation is a continuation of the effort to address the LFRG concerns by re-examining the radionuclide inventories associated with Fourmile Branch (FMB) IOU, Pen Branch (PB) IOU and Steel Creek (SC) IOU. The overall approach to computing radionuclide inventories for each of the IOUs involved the following components: • Defining contaminated reaches of sediments along the IOU waterways • Identifying separate segments within each IOU waterway to evaluate individually • Computing the volume and mass of contaminated soil associated with each segment, or “compartment” • Obtaining the available and appropriate Sediment and Sediment/Soil analytical results associated with each IOU • Standardizing all radionuclide activity by decay-correcting all sample analytical results from sample date to the current point in time, • Computing representative concentrations for all radionuclides associated with each compartment in each of the IOUs • Computing the
Bounded Rationality and Tacit Knowledge in the Organizational Capabilities Approach
Foss, Nikolaj J.
2004-01-01
The famous three chapters in Nelson and Winter (1982) that focus on firm routines and capabilities are often taken to be solidly founded on an assumption of bounded rationality. I argue that, in actuality, bounded rationality plays a rather limited role in Nelson and Winter (1982), that the very different assumption of tacit knowledge is much more central, and that the links between bounded rationality and routines/capabilities are not clear. I then argue that the absence in Nelson and Winter...
Decay parameter and related properties of 2-type branching processes
Institute of Scientific and Technical Information of China (English)
LI JunPing
2009-01-01
We consider the decay parameter, invariant measures/vectors and quasi-stationary dis-tributions for 2-type Markov branching processes. Investigating such properties is crucial in realizing life period of branching models. In this paper, some important properties of the generating functions for 2-type Markov branching q-matrix are firstly investigated in detail. The exact value of the decay parameter λC of such model is given for the communicating class C = Z+2\\ 0. It is shown that this λC can be directly obtained from the generating functions of the corresponding q-matrix. Moreover, the λC-invariant measures/vectors and quasi-distributions of such processes are deeply considered. A λC-invariant vector for the q-matrix (or for the process) on C is given and the generating functions of λC-invariant measures and quasi-stationary distributions for the process on C are presented.
Decay parameter and related properties of 2-type branching processes
Institute of Scientific and Technical Information of China (English)
2009-01-01
We consider the decay parameter, invariant measures/vectors and quasi-stationary dis- tributions for 2-type Markov branching processes. Investigating such properties is crucial in realizing life period of branching models. In this paper, some important properties of the generating functions for 2-type Markov branching q-matrix are firstly investigated in detail. The exact value of the decay parameter λC of such model is given for the communicating class C = Z+2 \\ 0. It is shown that this λC can be directly obtained from the generating functions of the corresponding q-matrix. Moreover, the λC-invariant measures/vectors and quasi-distributions of such processes are deeply considered. A λC-invariant vector for the q-matrix (or for the process) on C is given and the generating functions of λC-invariant measures and quasi-stationary distributions for the process on C are presented.
Tensor Squeezed Limits and the Higuchi Bound
Bordin, Lorenzo; Mirbabayi, Mehrdad; Noreña, Jorge
2016-01-01
We point out that tensor consistency relations-i.e. the behavior of primordial correlation functions in the limit a tensor mode has a small momentum-are more universal than scalar consistency relations. They hold in the presence of multiple scalar fields and as long as anisotropies are diluted exponentially fast. When de Sitter isometries are approximately respected during inflation this is guaranteed by the Higuchi bound, which forbids the existence of light particles with spin: De Sitter space can support scalar hair but no curly hair. We discuss two indirect ways to look for the violation of tensor con- sistency relations in observations, as a signature of models in which inflation is not a strong isotropic attractor, such as solid inflation: (a) Graviton exchange contribution to the scalar four-point function; (b) Quadrupolar anisotropy of the scalar power spectrum due to super-horizon tensor modes. This anisotropy has a well-defined statistics which can be distinguished from cases in which the background...
Branched polymers in restricted geometry : Flory theory, scaling and blobs
Vilgis, T.; Haronska, P.; Benhamou, M.
1994-01-01
This paper discusses the behavior of polymers with arbitrary connectivity in restricted geometries, such as pores and slaps. The use of Flory theories, blob models and scaling theories for linear chains is well-known and does not lead to any problems, i.e. all three approaches agree with each other. In the case of branched molecules this is not the case and e.g. no blob model exists. Indeed Flory free energies and scaling theories may lead to contradictions, when applied to branched objects a...
Composition and Structural Features of Calcium—Bound and Iron—and Aluminium—Bound Humus in Soils
Institute of Scientific and Technical Information of China (English)
S．U．CHEEMA; XUJIAN－MIN; 等
1994-01-01
Calcium-bound and iron-and aluminium-bound humus extracted from different soils collected from north to south of China were characterized by chemical and spectroscopic methods.Meaningful differences in the composition and structure between them were revealed by 13 C NMR,visible spectroscopy and elemental analysis.Results showed that the contents of carbon,hydrogen and nitrogen were higher in iron-and aluminium-bound humus than in calcium-bound humus while oxygen content in calcium-bound humus was shown to be higher .The calcium-bound humus had higher C/N and O/C ratios than iron-and aluminiumbound humus.The calcium-bound humic acid(HA1) showed higher E4/E6 ratios than iron-and aluminumboud,humic acid(HA2)while iron-and aluminum-bound fulvic acid(FA2) showed higher E4/E6 ratios than calcium-bound fulvic acid(FA1).An inverse relationship between E4/E6 ratios and aromaticity as determined by 13C NMR spectra was observerd for HA and FA from black soil.The 13C NMR spectroscopy revealed that HA2 was more aromatic than HA1.On the other ,FA1 exhibited a higher aromaticity than FA2.
Bounds on eigenvalues and singular values of interval matrices
Hladik, Milan; Daney, David; Tsigaridas, Elias P.,
2009-01-01
We study bounds on eigenvalues of interval matrices, and our aim is to develop fast computable formulae that produce as-sharp-as-possible bounds. We consider two cases: general (unsymmetric) and symmetric interval matrices. We focus on the latter case, since on one hand these such interval matrices have many applications in mechanics and engineering, and on the other many results from classical matrix analysis could be applied to them. We also provide bounds for the singular values of (genera...
Hydrocarbon metabolism by Brevibacterium erythrogenes: normal and branched alkanes.
Pirnik, M P; Atlas, R M; Bartha, R
1974-09-01
Branched- and straight-chain alkanes are metabolized by Brevibacterium erythrogenes by means of two distinct pathways. Normal alkanes (e.g., n-pentadecane) are degraded, after terminal oxidation, by the beta-oxidation system operational in fatty acid catabolism. Branched alkanes like pristane (2,6,10,14-tetramethylpentadecane) and 2-methylundecane are degraded as dicarboxylic acids, which also undergo beta-oxidation. Pristane-derived intermediates are observed to accumulate, with time, as a series of dicarboxylic acids. This dicarboxylic acid pathway is not observed in the presence of normal alkanes. Release of (14)CO(2) from [1-(14)C]pristane is delayed, or entirely inhibited, in the presence of n-hexadecane, whereas CO(2) release from n-hexadecane remains unaffected. These results suggest an inducible dicarboxylic acid pathway for degradation of branched-chain alkanes. PMID:4852318
Classical and quantum partition bound and detector inefficiency
Laplante, S; Roland, J
2012-01-01
In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, Jain and Klauck introduced the partition bound, which subsumes many of the known methods, in particular factorization norm, discrepancy, and the rectangle (corruption) bound. Physicists have considered a closely related scenario where two players share a predefined entangled state. Each is given a measurement as input, which they perform on their share of the system. The outcomes of the measurements follow a distribution which is predicted by quantum mechanics. In an experimental setting, Bell inequalities are used to distinguish truly quantum from classical behavior. We present a new lower bound technique based on the notion of detector inefficiency (where some runs are discarded by either of the players) for the ext...
Approach of generating parallel programs from parallelized algorithm design strategies
Institute of Scientific and Technical Information of China (English)
WAN Jian-yi; LI Xiao-ying
2008-01-01
Today, parallel programming is dominated by message passing libraries, such as message passing interface (MPI). This article intends to simplify parallel programming by generating parallel programs from parallelized algorithm design strategies. It uses skeletons to abstract parallelized algorithm design strategies, as well as parallel architectures. Starting from problem specification, an abstract parallel abstract programming language+ (Apla+) program is generated from parallelized algorithm design strategies and problem-specific function definitions. By combining with parallel architectures, implicity of parallelism inside the parallelized algorithm design strategies is exploited. With implementation and transformation, C++ and parallel virtual machine (CPPVM) parallel program is finally generated. Parallelized branch and bound (B&B) algorithm design strategy and parallelized divide and conquer (D & C) algorithm design strategy are studied in this article as examples. And it also illustrates the approach with a case study.
Upper bounds on minimum cardinality of exact and approximate reducts
Chikalov, Igor
2010-01-01
In the paper, we consider the notions of exact and approximate decision reducts for binary decision tables. We present upper bounds on minimum cardinality of exact and approximate reducts depending on the number of rows (objects) in the decision table. We show that the bound for exact reducts is unimprovable in the general case, and the bound for approximate reducts is almost unimprovable in the general case. © 2010 Springer-Verlag Berlin Heidelberg.
Three types of statistics and the entropy bounds
Xiao, Yong; Chen, Yi-Xin
2008-01-01
We investigated the entropy bounds of the three types of statistics: para-Bose, para-Fermi and infinite statistics. We showed that the entropy bounds of the conventional Bose, Fermi statistics and their generalizations to parastatistics obey the $A^{3/4}$ law, while the entropy bound of infinite statistics obeys the area law. This suggests a close relationship between infinite statistics and quantum gravity.
Scale dependence of branching in arterial and bronchial trees
Restrepo, J G; Hunt, B R; Restrepo, Juan G.; Ott, Edward; Hunt, Brian R.
2005-01-01
Although models of branching in arterial and bronchial trees often predict a dependence of bifurcation parameters on the scale of the bifurcating vessels, direct verifications of this dependence with data are uncommon. We compare measurements of bifurcation parameters in airways and arterial trees of different mammals as a function of scale to general features predicted by theoretical models. We find that the size dependence is more complex than existing theories based solely on energy minimization explain, and suggest additional factors that may govern the branching at different scales.
Coulomb branch Hilbert series and Three Dimensional Sicilian Theories
Cremonesi, Stefano; Mekareeya, Noppadol; Zaffaroni, Alberto
2014-01-01
We evaluate the Coulomb branch Hilbert series of mirrors of three dimensional Sicilian theories, which arise from compactifying the $6d$ $(2,0)$ theory with symmetry $G$ on a circle times a Riemann surface with punctures. We obtain our result by gluing together the Hilbert series for building blocks $T_{\\mathbf{\\rho}}(G)$, where $\\mathbf{\\rho}$ is a certain partition related to the dual group of $G$, which we evaluated in a previous paper. The result is expressed in terms of a class of symmetric functions, the Hall-Littlewood polynomials. As expected from mirror symmetry, our results agree at genus zero with the superconformal index prediction for the Higgs branch Hilbert series of the Sicilian theories and extend it to higher genus. In the $A_1$ case at genus zero, we also evaluate the Coulomb branch Hilbert series of the Sicilian theory itself, showing that it only depends on the number of external legs.
3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
Hertli, Timon
2011-01-01
The PPSZ algorithm by Paturi, Pudl\\'ak, Saks, and Zane [1998] is the fastest known algorithm for Unique k-SAT, where the input formula does not have more than one satisfying assignment. For k>=5 the same bounds hold for general k-SAT. We show that this is also the case for k=3,4, using a slightly modified PPSZ algorithm. We do the analysis by defining a cost for satisfiable CNF formulas, which we prove to decrease in each PPSZ step by a certain amount. This improves our previous best bounds with Moser and Scheder [2011] for 3-SAT from O(1.32065^n) to O(1.30704^n) and for 4-SAT from O(1.46928^n) to O(1.46899^n).
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. PMID:26830434
Branch and price for the time-dependent vehicle routing problem with time windows
DEFF Research Database (Denmark)
Dabia, Said; Van Woensel, Tom; De Kok, Ton;
2013-01-01
This paper presents a branch-and-price algorithm for the time-dependent vehicle routing problem with time windows (TDVRPTW). We capture road congestion by considering time-dependent travel times, i.e., depending on the departure time to a customer, a different travel time is incurred. We consider...... the variant of the TDVRPTW where the objective is to minimize total route duration and denote this variant the duration minimizing TDVRPTW (DM-TDVRPTW). Because of time dependency, vehicles' dispatch times at the depot are crucial as road congestion might be avoided. Because of its complexity, all...... means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. We introduce new dominance criteria that allow more label dominance. For our numerical results, we modified Solomon's data sets by adding time dependency. Our algorithm is able to solve about 63% of the...
Upper Bounds for the Euclidean Operator Radius and Applications
Directory of Open Access Journals (Sweden)
2009-02-01
Full Text Available The main aim of the present paper is to establish various sharp upper bounds for the Euclidean operator radius of an n-tuple of bounded linear operators on a Hilbert space. The tools used are provided by several generalizations of Bessel inequality due to Boas-Bellman, Bombieri, and the author. Natural applications for the norm and the numerical radius of bounded linear operators on Hilbert spaces are also given.
Upper Bounds for the Euclidean Operator Radius and Applications
Directory of Open Access Journals (Sweden)
Dragomir SS
2008-01-01
Full Text Available Abstract The main aim of the present paper is to establish various sharp upper bounds for the Euclidean operator radius of an -tuple of bounded linear operators on a Hilbert space. The tools used are provided by several generalizations of Bessel inequality due to Boas-Bellman, Bombieri, and the author. Natural applications for the norm and the numerical radius of bounded linear operators on Hilbert spaces are also given.
Graphene in inhomogeneous magnetic fields: bound, quasi-bound and scattering states
Energy Technology Data Exchange (ETDEWEB)
Ramezani Masir, M; Peeters, F M [Departement Fysica, Universiteit Antwerpen Groenenborgerlaan 171, B-2020 Antwerpen (Belgium); Vasilopoulos, P, E-mail: mrmphys@gmail.com, E-mail: takis@alcor.concordia.ca, E-mail: francois.peeters@ua.ac.be [Department of Physics, Concordia University, Montreal, Quebec, H4B 1R6 (Canada)
2011-08-10
The electron states in graphene-based magnetic dot and magnetic ring structures and combinations of both are investigated. The corresponding spectra are studied as a function of the radii, the strengths of the inhomogeneous magnetic field and of a uniform background field, the strength of an electrostatic barrier and the angular momentum quantum number. In the absence of an external magnetic field we have only long-lived quasi-bound and scattering states and we assess their influence on the density of states. In addition, we consider elastic electron scattering by a magnetic dot, whose average B vanishes, and show that the Hall and longitudinal resistivities, as a function of the Fermi energy, exhibit a pronounced oscillatory structure due to the presence of quasi-bound states. Depending on the dot parameters this oscillatory structure differs substantially for energies below and above the first Landau level.
ELEMENTARY DENSITY BOUNDS FOR SELF-SIMILAR SETS AND APPLICATION
Institute of Scientific and Technical Information of China (English)
无
2007-01-01
Falconer[1] used the relationship between upper convex density and upper spherical density to obtain elementary density bounds for s-sets at HS-almost all points of the sets. In this paper, following Falconer[1], we first provide a basic method to estimate the lower bounds of these two classes of set densities for the self-similar s-sets satisfying the open set condition (OSC), and then obtain elementary density bounds for such fractals at all of their points. In addition, we apply the main results to the famous classical fractals and get some new density bounds.
Boosting foundations and algorithms
Schapire, Robert E
2012-01-01
Boosting is an approach to machine learning based on the idea of creating a highly accurate predictor by combining many weak and inaccurate "rules of thumb." A remarkably rich theory has evolved around boosting, with connections to a range of topics, including statistics, game theory, convex optimization, and information geometry. Boosting algorithms have also enjoyed practical success in such fields as biology, vision, and speech processing. At various times in its history, boosting has been perceived as mysterious, controversial, even paradoxical.
Microscopic observation of magnon bound states and their dynamics
Fukuhara, Takeshi; Schauß, Peter; Endres, Manuel; Hild, Sebastian; Cheneau, Marc; Bloch, Immanuel; Gross, Christian
2013-01-01
More than eighty years ago, H. Bethe pointed out the existence of bound states of elementary spin waves in one-dimensional quantum magnets. To date, identifying signatures of such magnon bound states has remained a subject of intense theoretical research while their detection has proved challenging for experiments. Ultracold atoms offer an ideal setting to reveal such bound states by tracking the spin dynamics after a local quantum quench with single-spin and single-site resolution. Here we r...
RStorm: Developing and Testing Streaming Algorithms in R
Kaptein, M.C.
2014-01-01
Streaming data, consisting of indefinitely evolving sequences, are becoming ubiquitous in many branches of science and in various applications. Computer scientists have developed streaming applications such as Storm and the S4 distributed stream computing platform1 to deal with data streams. However, in current production packages testing and evaluating streaming algorithms is cumbersome. This paper presents RStorm for the development and evaluation of streaming algorithms analogous to these ...
Cutting Planes for Branch-and-Price Algorithms
DEFF Research Database (Denmark)
Desaulniers, Guy; Desrosiers, Jacques; Spoorendonk, Simon
2011-01-01
This article presents a general framework for formulating cutting planes in the context of column generation for integer programs. Valid inequalities can be derived using the variables of an equivalent compact formulation (i.e., the subproblem variables) or the master problem variables. In the fi...
An Efficient Algorithm for Upper Bound on the Partition Function of Nucleic Acids
Chitsaz, Hamidreza; Forouzmand, Elmirasadat; Haffari, Gholamreza
2013-01-01
It has been shown that minimum free energy structure for RNAs and RNA-RNA interaction is often incorrect due to inaccuracies in the energy parameters and inherent limitations of the energy model. In contrast, ensemble based quantities such as melting temperature and equilibrium concentrations can be more reliably predicted. Even structure prediction by sampling from the ensemble and clustering those structures by Sfold [7] has proven to be more reliable than minimum free energy structure pred...
Ground state and excitations of a Bose-Einstein condensate of atoms and their diatomic bound states
International Nuclear Information System (INIS)
We study theoretically a many-body system of spinless atoms and their diatomic bound states (or molecules) which form a single Bose-Einstein condensate at zero temperature. The equilibrium states of such a system and its dynamics are analyzed within the Gross-Pitaevskii approach. It is shown that the system exhibits two phases depending on binding energy value: it can be in the states with atomic-molecular condensate or molecular condensate. The basic thermodynamic characteristics of the two phases and their stability conditions are obtained. Both phases are characterized by two branches of collective excitations. The first branch is acoustic mode and the second one is gapfull
Directory of Open Access Journals (Sweden)
Amélie ePinet
2015-02-01
Full Text Available Plant branching is a key process in the yield elaboration of winter oilseed rape (WOSR. It is also involved in plant tolerance to flower damage because it allows the setting of new fertile inflorescences. Here we characterize the changes in the branching and distribution of the number of pods between primary and secondary inflorescences in response to floral bud clippings. Then we investigate the impacts of the modifications in branching on the biomass allocation and its consequence on the crop productivity (harvest index. These issues were addressed on plants with contrasted architecture and branching potential, using three genotypes (Exocet, Pollen, and Gamin grown under two levels of nitrogen fertilization. Clipping treatments of increasing intensities were applied to either inflorescences or flower buds.We were able to show that restoration of the number of pods after clipping is the main lever for the compensation. Genotypes presented different behaviors in branching and biomass allocation as a function of clipping treatments. The number of fertile ramifications increased for the high intensities of clipping. In particular, the growth of secondary ramifications carried by branches developed before clipping has been observed. The proportions of yield and of number of pods carried by these secondary axes increased and became almost equivalent to the proportion carried by primary inflorescences. In terms of biomass allocation, variations have also been evidenced in the relationship between pod dry mass on a given axis and the number of pods set, while the shoot/root ratio was not modified. The harvest index presented different responses: it decreased after flower buds clipping, while it was maintained after the clipping of the whole inflorescences. The results are discussed relative to their implications regarding the identification of interesting traits to be target in breeding programs in order to improve WOSR tolerance.
Energy Technology Data Exchange (ETDEWEB)
Symbalisty, E.M.D.; Zinn, J.; Whitaker, R.W.
1995-09-01
This paper describes the history, physics, and algorithms of the computer code RADFLO and its extension HYCHEM. RADFLO is a one-dimensional, radiation-transport hydrodynamics code that is used to compute early-time fireball behavior for low-altitude nuclear bursts. The primary use of the code is the prediction of optical signals produced by nuclear explosions. It has also been used to predict thermal and hydrodynamic effects that are used for vulnerability and lethality applications. Another closely related code, HYCHEM, is an extension of RADFLO which includes the effects of nonequilibrium chemistry. Some examples of numerical results will be shown, along with scaling expressions derived from those results. We describe new computations of the structures and luminosities of steady-state shock waves and radiative thermal waves, which have been extended to cover a range of ambient air densities for high-altitude applications. We also describe recent modifications of the codes to use a one-dimensional analog of the CAVEAT fluid-dynamics algorithm in place of the former standard Richtmyer-von Neumann algorithm.
Scaling properties of crack branching and brittle fragmentation
Directory of Open Access Journals (Sweden)
Uvarov S.
2011-01-01
Full Text Available The present study is focused on the correlation of scaling properties of crack branching and brittle fragmentation with damage accumulation and a change in the fracture mechanism. The experimental results obtained from the glass fragmentation tests indicate that the size distribution of fragments has a fractal character and is described by a power law.
Special branches: organic greenhouse production, bulbs, ornamentals and aquaculture
Sukkel, W.; Hommes, M.; Meijer, R.J.M.
2009-01-01
Organic production methods are gaining ground in Dutch specialised production branches. Interest is growing among greenhouse horticulturalists and growers of flower bulbs, ornamentals and mushrooms. In organic horticulture Dutch research is unique in the world in thinking up innovative concepts and
Design and Calculation of the New Distribution Network Branch
Frechová, L.
2015-01-01
The aim of the project is to provide a summary about design and calculation of the new distribution network branch. It solves the problem of the selection of a suitable transformer and conductor and it shows results of application of base calculation methods.
Bound pesticide residues in soils and plants and their determination
International Nuclear Information System (INIS)
To assess the environmental significance of pesticide residues in soil and plants one must distinguish between two types of residues: those that are extractable with solvents, and those residues that are not extractable with solvent. The extent of bound (non-extractable) residues varies with the plant and pesticide involved and generally increases with time after treatment Bound pesticide residues have been detected in the organic matter fractions of soil, i.e. humic acid, fulvic acid and humin. Several studies have shown that lignin, hemicellulose and pectic polysaccharide are the major bound residues fraction of pesticide in plants. Attempts have been made to extract bound pesticide residues by the milder to harsher methods. Drastic extractive procedures destroy the structure of soil or plants often results in the destruction of the identity of bound residues. The High Temperature Distillation (HTD) and Supercritical Fluid Extraction (SFE) techniques may provide possible means for extraction and identification of bound residues in food products. Regulatory agencies should also consider placing further emphasis on employing more effective extraction techniques and procedures to quantitatively remove bound residues
Algorithms for Scheduling Weighted Packets with Deadlines in a Bounded Queue
LI Fei
2008-01-01
Motivated by the Quality-of-Service (QoS) buffer management problem, we consider online scheduling of packets with hard deadlines in a finite capacity queue. At any time, a queue can store at most $b \\in \\mathbb Z^+$ packets. Packets arrive over time. Each packet is associated with a non-negative value and an integer deadline. In each time step, only one packet is allowed to be sent. Our objective is to maximize the total value gained by the packets sent by their deadlines in an online manner...
Bounded cascade clouds: albedo and effective thickness
Cahalan, R. F.
2002-01-01
If climate models produced clouds having liquid water amounts close to those observed, they would compute a mean albedo that is often much too large, due to the treatment of clouds as plane-parallel. An approximate lower-bound for this "plane-parallel albedo bias" may be obtained from a fractal model having a range of optical thicknesses similar to those observed in marine stratocumulus, since they are more nearly plane-parallel than most other cloud types. We review ...
Improved algorithms for mapping pipelined and parallel computations
Nicol, David M.; O'Hallaron, David R.
1991-01-01
Recent work on the problem of mapping pipelined or parallel computations onto linear array, shared memory, and host-satellite systems is extended. It is shown how these problems can be solved even more efficiently when computation module execution times are bounded from below, intermodule communication times are bounded from above, and the processors satisfy certain homogeneity constraints. The improved algorithms have significantly lower time and space complexities than the more general algorithms: in one case, an O(nm3) time algorithm for mapping m modules onto n processors is replaced with an O(nm log m) time algorithm, and the space requirements are reduced from O(nm2) to O(m). Run-time complexity is reduced further with parallel mapping algorithms based on these improvements, which run on the architectures for which they create mappings.
MYOCARDIAL DEFORMATION AND COMPLETE LEFT BUNDLE BRANCH BLOCK
Directory of Open Access Journals (Sweden)
E. N. Pavlyukova
2015-12-01
Full Text Available Tissue Doppler imaging is evolving as a useful echocardiographic tool for quantitative assessment of left ventricular systolic and diastolic function. Over the last 10 years, myocardial deformation imaging has become possible initially with tissue Doppler , and more recently with myocardial speckle-tracking using 2D echocardiography. Unlike simple tissue velocity measurements, deformation measurements are specific for the region of interest. Strain rate or strain measurements have been used as sensitive indicators for subclinical diseases, and it is the most widely used tool to assess mechanical dyssynchrony. Left bundle branch block is a frequent, etiologically heterogeneous, clinically hostile and diagnostically challenging entity. About 2% of patients underwent cardiac stress testing show stable or intermittent left bundle branch block. Presence of left bundle branch block is associated with a lower and slower diastolic coronary flow velocity especially during hyperemia. Stress echocardiography is the best option for the diagnosis of ischemic heart disease, albeit specificity and sensitivity reduce in patients with left bundle branch block in the territory of left anterior descending artery in presence of initial septum dyskinesia.
Branch Campus Librarianship with Minimal Infrastructure: Rewards and Challenges
Knickman, Elena; Walton, Kerry
2014-01-01
Delaware County Community College provides library services to its branch campus community members by stationing a librarian at a campus 5 to 20 hours each week, without any more library infrastructure than an Internet-enabled computer on the school network. Faculty and students have reacted favorably to the increased presence of librarians.…
Institute of Scientific and Technical Information of China (English)
2007-01-01
Based on the exact analytical solution of ordinary differential equations, a truncation of the Taylor series of the exact solution to the Nth order leads to the Nth order algebraic dynamics algorithm. A detailed numerical comparison is presented with Runge-Kutta algorithm and symplectic geometric algorithm for 12 test models. The results show that the algebraic dynamics algorithm can better preserve both geometrical and dynamical fidelity of a dynamical system at a controllable precision, and it can solve the problem of algorithm-induced dissipation for the Runge-Kutta algorithm and the problem of algorithm-induced phase shift for the symplectic geometric algorithm.
Institute of Scientific and Technical Information of China (English)
WANG ShunJin; ZHANG Hua
2007-01-01
Based on the exact analytical solution of ordinary differential equations,a truncation of the Taylor series of the exact solution to the Nth order leads to the Nth order algebraic dynamics algorithm.A detailed numerical comparison is presented with Runge-Kutta algorithm and symplectic geometric algorithm for 12 test models.The results show that the algebraic dynamics algorithm can better preserve both geometrical and dynamical fidelity of a dynamical system at a controllable precision,and it can solve the problem of algorithm-induced dissipation for the Runge-Kutta algorithm and the problem of algorithm-induced phase shift for the symplectic geometric algorithm.
Roles for auxin, cytokinin, and strigolactone in regulating shoot branching.
Ferguson, Brett J; Beveridge, Christine A
2009-04-01
Many processes have been described in the control of shoot branching. Apical dominance is defined as the control exerted by the shoot tip on the outgrowth of axillary buds, whereas correlative inhibition includes the suppression of growth by other growing buds or shoots. The level, signaling, and/or flow of the plant hormone auxin in stems and buds is thought to be involved in these processes. In addition, RAMOSUS (RMS) branching genes in pea (Pisum sativum) control the synthesis and perception of a long-distance inhibitory branching signal produced in the stem and roots, a strigolactone or product. Auxin treatment affects the expression of RMS genes, but it is unclear whether the RMS network can regulate branching independently of auxin. Here, we explore whether apical dominance and correlative inhibition show independent or additive effects in rms mutant plants. Bud outgrowth and branch lengths are enhanced in decapitated and stem-girdled rms mutants compared with intact control plants. This may relate to an RMS-independent induction of axillary bud outgrowth by these treatments. Correlative inhibition was also apparent in rms mutant plants, again indicating an RMS-independent component. Treatments giving reductions in RMS1 and RMS5 gene expression, auxin transport, and auxin level in the main stem were not always sufficient to promote bud outgrowth. We suggest that this may relate to a failure to induce the expression of cytokinin biosynthesis genes, which always correlated with bud outgrowth in our treatments. We present a new model that accounts for apical dominance, correlative inhibition, RMS gene action, and auxin and cytokinin and their interactions in controlling the progression of buds through different control points from dormancy to sustained growth. PMID:19218361
Join-Graph Propagation Algorithms
Mateescu, Robert; Kask, Kalev; Gogate, Vibhav; Dechter, Rina
2014-01-01
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with a...
Genetic Algorithms and Local Search
Whitley, Darrell
1996-01-01
The first part of this presentation is a tutorial level introduction to the principles of genetic search and models of simple genetic algorithms. The second half covers the combination of genetic algorithms with local search methods to produce hybrid genetic algorithms. Hybrid algorithms can be modeled within the existing theoretical framework developed for simple genetic algorithms. An application of a hybrid to geometric model matching is given. The hybrid algorithm yields results that improve on the current state-of-the-art for this problem.
Nuclear Science and Technology Branch Report 1975
International Nuclear Information System (INIS)
A summary is given of research activities. These include: nuclear techniques of analysis, nuclear techniques in hydrology, industrial applications of radioisotopes, biological and chemical applications of irradiation, radiation detection and measurement, environmental studies and biophysics and radiation biology. Patent applications and staff of the nuclear science and applications secretariat are listed. (R.L.)
Nuclear science and technology branch report 1977
International Nuclear Information System (INIS)
A summary is given of research activities. These include: nuclear techniques of analysis, isotope techniques in hydrology, industrial applications of radioisotopes, biological and chemical applications of radiation, radiation detection and measurement, environmental studies, biophysics and radiation biology. (J.R.)
Nanocrystals with linear and branched topology
Alivisatos, A. Paul; Milliron, Delia; Manna, Liberato; Hughes, Steven M.
2007-12-04
Disclosed herein are nanostructures comprising distinct dots and rods coupled through potential barriers of tuneable height and width, and arranged in three dimensional space at well defined angles and distances. Such control allows investigation of potential applications ranging from quantum information processing to artificial photosynthesis.
Nuclear science and technology branch report 1976
International Nuclear Information System (INIS)
Research being conducted includes: assessment of world energy sources and their utilization, basic information on fission reactors, reactor performance and safety, reviews of fission reactor technology, collaborative work on fission reactors, thermonuclear fusion and alternative energy sources. Staff publications and research interests are outlined. (J.R.)
Nuclear Science and Technology Branch report 1977
International Nuclear Information System (INIS)
A report of research programs continuing in the following areas is presented: mining and treatment of uranium ores, manufacture of uranium hexafluoride, uranium enrichment, waste treatment, reprocessing and the uranium fuel cycle. Staff responsible for each project are indicated
Energy conditions bounds and their confrontation with supernovae data
Lima, M P; Rebouças, M J
2008-01-01
The energy conditions play an important role in the understanding of several properties of the Universe, including the current accelerating expansion phase and the possible existence of the so-called phantom fields. We show that the integrated bounds provided by the energy conditions on cosmological observables such as the distance modulus $\\mu(z)$ and the lookback time $t_L(z)$ are not sufficient (nor necessary) to ensure the local fulfillment of the energy conditions, making explicit the limitation of these bounds in the confrontation with observational data. We recast the energy conditions as bounds on the deceleration and normalized Hubble parameters, obtaining new bounds which are necessary and sufficient for the local fulfillment of the energy conditions. A statistical confrontation, with $1\\sigma$ confidence level, between our bounds and supernovae data from the gold and combined samples is made for the recent past ($z \\leq 1$). Our analyses indicate the fulfillment of the weak and dominant energy cond...
Nuclear science and technology branch report 1975
International Nuclear Information System (INIS)
Research programs are reported for the following divisions: Engineering Research, Chemical Technology, Instrumentation and Control, Materials division, Isotopes, Physics, Health Physics, Applied Mathematics and Computing, Radiation Biology Research. The names of staff responsible for each project are indicated. (R.L.)
Nuclear Science and Technology Branch report 1977
International Nuclear Information System (INIS)
This report records the technical service provided in support of research programs at the Research Establishment. Such services include HIFAR reactor operations, engineering services, information services, safety services and services provided research divisions themselves. Radioisotope production and other commercial activities are also included
Genetic Algorithms and Quantum Computation
Giraldi, Gilson A.; Portugal, Renato; Thess, Ricardo N.
2004-01-01
Recently, researchers have applied genetic algorithms (GAs) to address some problems in quantum computation. Also, there has been some works in the designing of genetic algorithms based on quantum theoretical concepts and techniques. The so called Quantum Evolutionary Programming has two major sub-areas: Quantum Inspired Genetic Algorithms (QIGAs) and Quantum Genetic Algorithms (QGAs). The former adopts qubit chromosomes as representations and employs quantum gates for the search of the best ...
Combinatorial optimization algorithms and complexity
Papadimitriou, Christos H
1998-01-01
This clearly written, mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering.
Viscosity bound violation in holographic solids and the viscoelastic response
Alberte, Lasma; Pujolas, Oriol
2016-01-01
We argue that the Kovtun--Son--Starinets (KSS) lower bound on the viscosity to entropy density ratio holds in fluid systems but is violated in solid materials with a non-zero shear elastic modulus. We construct explicit examples of this by applying the standard gauge/gravity duality methods to massive gravity and show that the KSS bound is clearly violated in black brane solutions whenever the massive gravity theories are of solid type. We argue that the physical reason for the bound violation relies on the viscoelastic nature of the mechanical response in these materials. We speculate on whether any real-world materials can violate the bound and discuss a possible generalization of the bound that involves the ratio of the shear elastic modulus to the pressure.
Evolutionary Algorithms and Dynamic Programming
Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian
2013-01-01
Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how ...
Ratkanthwar, Kedar
2013-01-01
An exact comb polyisoprene (PI) with three branches, with the middle branch having twice the molecular weight of the two other identical external branches, was synthesized by using anionic polymerization high vacuum techniques and appropriate chlorosilane chemistry. The synthetic approach involves (a) the selective replacement of the two chlorines of 4-(dichloromethylsilyl) diphenylethylene (DCMSDPE, key molecule) with identical PI chains by titration with PILi, (b) the addition of sec-BuLi to the double bond of DPE followed by the polymerization of isoprene from the newly created anionic site to form a 3-arm living star PI, (c) the selective replacement of the two chlorines of trichloromethylsilane with 3-arm star PI to form an H-shape intermediate, and (d) the replacement of the remaining chlorine of trichloromethylsilane by linear PI chains with double the molecular weight. All intermediate and final products were characterized via size exclusion chromatography, temperature gradient interaction chromatography and 1H-NMR spectroscopy. As expected, due to the inability to control the exact stoichiometry of the linking reactants, the main product (exact comb PI) is contaminated by a few by-products, despite the fact that anionic polymerization is the most efficient way to produce well-defined polymers. © 2013 The Royal Society of Chemistry.
Genetic Algorithm for Optimization: Preprocessor and Algorithm
Sen, S. K.; Shaykhian, Gholam A.
2006-01-01
Genetic algorithm (GA) inspired by Darwin's theory of evolution and employed to solve optimization problems - unconstrained or constrained - uses an evolutionary process. A GA has several parameters such the population size, search space, crossover and mutation probabilities, and fitness criterion. These parameters are not universally known/determined a priori for all problems. Depending on the problem at hand, these parameters need to be decided such that the resulting GA performs the best. We present here a preprocessor that achieves just that, i.e., it determines, for a specified problem, the foregoing parameters so that the consequent GA is a best for the problem. We stress also the need for such a preprocessor both for quality (error) and for cost (complexity) to produce the solution. The preprocessor includes, as its first step, making use of all the information such as that of nature/character of the function/system, search space, physical/laboratory experimentation (if already done/available), and the physical environment. It also includes the information that can be generated through any means - deterministic/nondeterministic/graphics. Instead of attempting a solution of the problem straightway through a GA without having/using the information/knowledge of the character of the system, we would do consciously a much better job of producing a solution by using the information generated/created in the very first step of the preprocessor. We, therefore, unstintingly advocate the use of a preprocessor to solve a real-world optimization problem including NP-complete ones before using the statistically most appropriate GA. We also include such a GA for unconstrained function optimization problems.
Agriculture and Food Processes Branch program summary document
Energy Technology Data Exchange (ETDEWEB)
None
1980-06-01
The work of the Agriculture and Food Processes Branch within the US DOE's Office of Industrial Programs is discussed and reviewed. The Branch is responsible for assisting the food and agricultural sectors of the economy in increasing their energy efficiency by cost sharing with industry the development and demonstration of technologies industry by itself would not develop because of a greater than normal risk factor, but have significant energy conservation benefits. This task is made more difficult by the diversity of agriculture and the food industry. The focus of the program is now on the development and demonstration of energy conservation technology in high energy use industry sectors and agricultural functions (e.g., sugar processing, meat processing, irrigation, and crop drying, high energy use functions common to many sectors of the food industry (e.g., refrigeration, drying, and evaporation), and innovative concepts (e.g., energy integrated farm systems. Specific projects within the program are summarized. (LCL)
Trimmed Moebius Inversion and Graphs of Bounded Degree
Björklund, Andreas; Kaski, Petteri; Koivisto, Mikko
2008-01-01
We study ways to expedite Yates's algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an $n$-element universe $U$ and a family $\\scr F$ of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of $U$ with $k$ sets from $\\scr F$ in time within a polynomial factor (in $n$) of the number of supersets of the members of $\\scr F$. Relying on an intersection theorem of Chung et al. (1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs of maximum degree $\\Delta$. In particular, we show how to compute the Domatic Number in time within a polynomial factor of $(2^{\\Delta+1-2)^{n/(\\Delta+1)$ and the Chromatic Number in time within a polynomial factor of $(2^{\\Delta+1-\\Delta-1)^{n/(\\Delta+1)$. F...
Vertex Sparsifiers and Abstract Rounding Algorithms
Charikar, Moses; Li, Shi; Moitra, Ankur
2010-01-01
The notion of vertex sparsification is introduced in \\cite{M}, where it was shown that for any graph $G = (V, E)$ and a subset of $k$ terminals $K \\subset V$, there is a polynomial time algorithm to construct a graph $H = (K, E_H)$ on just the terminal set so that simultaneously for all cuts $(A, K-A)$, the value of the minimum cut in $G$ separating $A$ from $K -A$ is approximately the same as the value of the corresponding cut in $H$. We give the first super-constant lower bounds for how well a cut-sparsifier $H$ can simultaneously approximate all minimum cuts in $G$. We prove a lower bound of $\\Omega(\\log^{1/4} k)$ -- this is polynomially-related to the known upper bound of $O(\\log k/\\log \\log k)$. This is an exponential improvement on the $\\Omega(\\log \\log k)$ bound given in \\cite{LM} which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers. Despite this negative result, we show that for many natural problems, we do not need to incur a multiplicative penalty fo...
Remarks and rigorous bounds relating to the decay Z → πγ and its relationship to the anomaly
International Nuclear Information System (INIS)
In this paper, it is rigorously shown that the amplitude for the decay Z → πγ must fall at least as fast as M-1z. Consequently its branching ratio must be smaller than 10-4; with slightly less conservative assumptions, this limit reduces to 5 x 10 -6. The anomaly, the triangle graph and the Ward identities are shown to be consistent with both these bounds and the rate for π0 → 2γ
Brachial plexus variations in its formation and main branches
Valéria Paula Sassoli Fazan; André de Souza Amadeu; Adilson L. Caleffi; Omar Andrade Rodrigues Filho
2003-01-01
PURPOSE: The brachial plexus has a complex anatomical structure since its origin in the neck throughout its course in the axillary region. It also has close relationship to important anatomic structures what makes it an easy target of a sort of variations and provides its clinical and surgical importance. The aims of the present study were to describe the brachial plexus anatomical variations in origin and respective branches, and to correlate these variations with sex, color of the subjects ...
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
We study the problem of root extraction in finite Abelian groups, where the group order is unknown. This is a natural generalization of the problem of decrypting RSA ciphertexts. We study the complexity of this problem for generic algorithms, that is, algorithms that work for any group and do 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...... implement 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...
Precision Polyolefin Structure: Modeling Polyethylene Containing Methyl and Ethyl Branches
Rojas, Giovanni; Wagener, Kenneth B.
Sequenced copolymers of ethylene and diverse species have been created using acyclic diene metathesis (ADMET) polymerization, a step growth, condensation- type polymerization driven to high conversion by the removal of ethylene. ADMET permits control over branch content and branch length, which can be predetermined during the monomer synthesis, allowing sequence control in the resultant unsaturated polymer. Monomers are symmetrical α,ωdienes with a pendant functionality. Diverse functional groups are compatible with ADMET polymerization when Schrock’s or first-generation Grubb’s catalysts are used. Saturation with hydrogen after ADMET polymerization affords a polyethylene (PE) backbone bearing specific functionalities in precise places. Varying both the pendant functional group and the spacing between functionalities alters the physical and chemical properties of the polymer. Incorporation of alkyl chains into the PE backbone via ADMET leads to the study of perfect structures modeling the copolymerization of ethylene with α-olefins such as 1-propene, 1-butene, 1-hexene, and 1-octene.
Superconducting film magnetic flux transformer with micro- and nanosized branches
Directory of Open Access Journals (Sweden)
Levan Ichkitidze
2013-06-01
Full Text Available The object of the study is a superconducting film magnetic flux transformer comprising two square shaped loops with the tapering active strips and a magnetosensitive film element between them. It is shown that splitting of the active strips into parallel micro- and nanosized superconducting branches and slits increases the gain factor of the transformer, i. e., the concentration of an external magnetic field on the magnetosensitive element, by a factor of more than four.
Dimension of branching processes and self-organized criticality
International Nuclear Information System (INIS)
Branching processes and their application as a model of self-organized criticality are briefly reviewed. The critical dimension for this model is calculated. The differences between our result and similar ones on polymers and percolation are explained. We discuss semiquantitatively why the critical dimension of a model of self-organized criticality that includes the oscillation of the sandpile around its critical value would be different, perhaps even infinite. Finally, we conjecture that our mathematical results are more general than they seem
Rivera, J. M.; Simpson, R. W.
1980-01-01
The aerial relay system network design problem is discussed. A generalized branch and bound based algorithm is developed which can consider a variety of optimization criteria, such as minimum passenger travel time and minimum liner and feeder operating costs. The algorithm, although efficient, is basically useful for small size networks, due to its nature of exponentially increasing computation time with the number of variables.
Rigorous Performance Bounds for Quadratic and Nested Dynamical Decoupling
Xia, Yuhou; Lidar, Daniel A
2011-01-01
We present rigorous performance bounds for the quadratic dynamical decoupling (QDD) pulse sequence which protects a qubit from general decoherence, and for its nested generalization to an arbitrary number of qubits. Our bounds apply under the assumption of instantaneous pulses and of bounded perturbing environment and qubit-environment Hamiltonians such as those realized by baths of nuclear spins in quantum dots. We prove that if the total sequence time is fixed then the trace-norm distance between the unperturbed and protected system states can be made arbitrarily small by increasing the number of applied pulses.
Proton binding by linear, branched, and hyperbranched polyelectrolytes
Koper, G.J.M.; Borkovec, M.
2010-01-01
This article reviews our understanding of ionization processes of weak polyelectrolytes. The emphasis is put on a general introduction to site binding models, which are able to account for many experimental features of linear and branched polyelectrolytes, including dendrimers. These models are fully compatible with the classical description of acid-base equilibria. The review further discusses the nature of the site-site interaction and role of conformational equilibria. Experimental chargin...
Public Relations as Scientific Branch of Information and Communication Sciences
Hrvoje Jakopović
2012-01-01
Given that the field of information and communication sciences is a young field in the social sciences, it is important to consider how technology impacts the development of this field. This is especially relevant when looking at the area of public relations. Amid changing technological developments public relations is constantly being redefined in this complex environment. This work focuses on the development of public relations as a branch of study in the field of information and communicat...
International Nuclear Information System (INIS)
This paper investigates second-order consensus of multi-agent systems with a virtual leader of varying velocity while preserving network connectivity. We propose a novel second-order consensus algorithm with bounded control inputs. Under the condition that the initial network is connected, the network will be connected all the time and all agents and the virtual leader can attain the same position and move with the same velocity. A simulation example is proposed to illustrate the effective of the proposed algorithm. (general)
Institute of Scientific and Technical Information of China (English)
孙光甦
2012-01-01
This paper investigates second-order consensus of multi-agent systems with a virtual leader of varying velocity while preserving network connectivity.We propose a novel second-order consensus algorithm with bounded control inputs.Under the condition that the initial network is connected,the network will be connected all the time and all agents and the virtual leader can attain the same position and move with the same velocity.A simulation example is proposed to illustrate the effective of the proposed algorithm.
Opposite Degree Algorithm and Its Applications
Directory of Open Access Journals (Sweden)
Xiao-Guang Yue
2015-12-01
Full Text Available The opposite (Opposite Degree, referred to as OD algorithm is an intelligent algorithm proposed by Yue Xiaoguang et al. Opposite degree algorithm is mainly based on the concept of opposite degree, combined with the idea of design of neural network and genetic algorithm and clustering analysis algorithm. The OD algorithm is divided into two sub algorithms, namely: opposite degree - numerical computation (OD-NC algorithm and opposite degree - Classification computation (OD-CC algorithm.
Opposite Degree Algorithm and Its Applications
Xiao-Guang Yue
2015-01-01
The opposite (Opposite Degree, referred to as OD) algorithm is an intelligent algorithm proposed by Yue Xiaoguang et al. Opposite degree algorithm is mainly based on the concept of opposite degree, combined with the idea of design of neural network and genetic algorithm and clustering analysis algorithm. The OD algorithm is divided into two sub algorithms, namely: opposite degree - numerical computation (OD-NC) algorithm and opposite degree - Classification computation (OD-CC) algorithm.
Valence-bound and diffuse-bound anions of 5-azauracil.
Corzo, H H; Dolgounitcheva, O; Zakrzewski, V G; Ortiz, J V
2014-08-28
Structures, isomerization energies, and electron binding energies of 5-azauracil and its anions have been calculated ab initio with perturbative, coupled-cluster, and electron-propagator methods. Tautomeric structures, including those produced by proton transfer to a CH group, have been considered. Dyson orbitals and pole strengths from electron-propagator calculations validated a simple, molecular-orbital picture of anion formation. In one case, an electron may enter a delocalized π orbital, yielding a valence-bound (VB) anion with a puckered ring structure. The corresponding electron affinity is 0.27 eV; the vertical electron detachment energy (VEDE) of this anion 1.05 eV. An electron also may enter a molecular orbital that lies outside the nuclear framework, resulting in a diffuse-bound (DB) anion. In the latter case, the electron affinity is 0.06 eV and the VEDE of the DB anion is 0.09 eV. Another VB isomer that is only 0.02 eV more stable than the neutral molecule has a VEDE of 2.0 eV. PMID:25102270
Complete manifolds with bounded curvature and spectral gaps
Schoen, Richard; Tran, Hung
2016-08-01
We study the spectrum of complete noncompact manifolds with bounded curvature and positive injectivity radius. We give general conditions which imply that their essential spectrum has an arbitrarily large finite number of gaps. In particular, for any noncompact covering of a compact manifold, there is a metric on the base so that the lifted metric has an arbitrarily large finite number of gaps in its essential spectrum. Also, for any complete noncompact manifold with bounded curvature and positive injectivity radius we construct a metric uniformly equivalent to the given one (also of bounded curvature and positive injectivity radius) with an arbitrarily large finite number of gaps in its essential spectrum.
Hodograph computation and bound estimation for rational B-spline curves
Institute of Scientific and Technical Information of China (English)
无
2007-01-01
It is necessary to compute the derivative and estimate the bound of rational B-spline curves in design system, which has not been studied to date. To improve the function of computer aided design (CAD) system, and to enhance the efficiency of different algorithms of rational B-spline curves, the representation of scaled hodograph and bound of derivative magnitude of uniform planar rational B-spline curves are derived by applying Dir function, which indicates the direction of Cartesian vector between homogeneous points, discrete B-spline theory and the formula of translating the product into a summation of B-spline functions. As an application of the result above,upper bound of parametric distance between any two points in a uniform planar rational B-spline curve is further presented.
LAX and SPA: Major regulators of shoot branching in rice
Komatsu, Keishi; Maekawa, Masahiko; Ujiie, Shin; Satake, Yuzuki; Furutani, Ikuyo; Okamoto, Hironobu; Shimamoto, Ko; Kyozuka, Junko
2003-01-01
The aerial architecture of plants is determined primarily by the pattern of shoot branching. Although shoot apical meristem initiation during embryogenesis has been extensively studied by molecular genetic approaches using Arabidopsis, little is known about the genetic mechanisms controlling axillary meristem initiation, mainly because of the insufficient number of mutants that specifically alter it. We identified the LAX PANICLE (LAX) and SMALL PANICLE (SPA) genes as the main regulators of a...
Lower Bounds on Implementing Robust and Resilient Mediators
Abraham, Ittai; Dolev, Danny; Halpern, Joseph Y.
2007-01-01
We consider games that have (k,t)-robust equilibria when played with a mediator, where an equilibrium is (k,t)-robust if it tolerates deviations by coalitions of size up to k and deviations by up to $t$ players with unknown utilities. We prove lower bounds that match upper bounds on the ability to implement such mediators using cheap talk (that is, just allowing communication among the players). The bounds depend on (a) the relationship between k, t, and n, the total number of players in the ...
Affinity- and topology-dependent bound on current fluctuations
Pietzonka, Patrick; Seifert, Udo
2016-01-01
We provide a proof of a recently conjectured universal bound on current fluctuations in Markovian processes. This bound establishes a link between the fluctuations of an individual observable current, the cycle affinities driving the system into a non-equilibrium steady state, and the topology of the network. The proof is based on a decomposition of the network into independent cycles with both positive affinity and positive stationary cycle current. This formalism allows for a refinement of the bound for systems in equilibrium or with locally vanishing affinities.
Vulnerable Derivatives and Good Deal Bounds: A Structural Model
DEFF Research Database (Denmark)
Murgoci, Agatha
2013-01-01
new restriction in the arbitrage free model by setting upper bounds on the Sharpe ratios (SRs) of the assets. The potential prices that are eliminated represent unreasonably good deals. The constraint on the SR translates into a constraint on the stochastic discount factor. Thus, tight pricing bounds...... can be obtained. We provide a link between the objective probability measure and the range of potential risk-neutral measures, which has an intuitive economic meaning. We also provide tight pricing bounds for European calls and show how to extend the call formula to pricing other financial products in...
Spectral bounds for percolation on directed and undirected graphs
Hamilton, Kathleen E.; Pryadko, Leonid P.
2015-01-01
We give several algebraic bounds for percolation on directed and undirected graphs: proliferation of strongly-connected clusters, proliferation of in- and out-clusters, and the transition associated with the number of giant components.
Institute of Scientific and Technical Information of China (English)
郑延斌; 郭凌云; 王宁
2012-01-01
Objective: to explore the correlation between metacognition ability and athletic ability of track man. Methods: by using questionnaire survey method , all date of metacognition ability grade is obtained. SPSS I 3. 0 for windows is employed in this paper to statistical analysis. Results:(1) for masters of sports and the second grade sportsmen, the first grade sportsmen and the second grade sportsmen,masters of sports and the second grade sportsmen,the significant differences do exist(P<< 0. 05);even there are remarkable significant differences between masters of sports and the second grade sportsmen(P<0. 01) , (2)metacognition ability are positively correlated to athletic ability of track man. Conclusions:metacognition ability does improve athletic ability of track man.%针对如何提高碰撞检测的实时性,提出了一种碰撞检测算法.该算法首先利用空间分解确定相邻物体,然后对相邻物体利用层次包围盒方法进行碰撞检测,在包围盒碰撞检测方面,提出了一种新的包围盒混合结构,这种混合结构结合了AABB包围盒相交测试的简单性和k-DOPs包围盒的紧密性.实验结果表明,该算法有效地提高了碰撞检测的实时性.
International Nuclear Information System (INIS)
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 τ+τ-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.)
The Coin Problem and Pseudorandomness for Branching Programs
DEFF Research Database (Denmark)
Brody, Joshua; Verbin, Elad
The emph{Coin Problem} is the following problem: a coin is given, which lands on head with probability either $1/2 + beta$ or $1/2 - beta$. We are given the outcome of $n$ independent tosses of this coin, and the goal is to guess which way the coin is biased, and to answer correctly with...... the model of emph{read-once width-$w$ branching programs}. We prove that in order to succeed in this model, $beta$ must be at least $1/ (log n)^{Theta(w)}$. For constant $w$ this is tight by considering the recursive tribes function, and for other values of $w$ this is nearly tight by considering...... cannot be distinguished by small-width read-once branching programs. We suggest one application for this kind of theorems: we prove that Nisan's Generator fools width-$w$ read-once emph{regular} branching programs, using seed length $O(w^4 log n log log n + log n log (1/eps))$. For $w=eps=Theta(1)$, this...
Quantum Algorithms for Finding Claws, Collisions and Triangles
Buhrman, H; Hoyer, P; Magniez, F; Santha, M; De Wolf, R; Buhrman, Harry; Durr, Christoph; Hoyer, Peter; Magniez, Frederic; Santha, Miklos; Wolf, Ronald de
2000-01-01
We present several applications of quantum amplitude amplification to finding claws and collisions in ordered or unordered functions. Our algorithms generalize those of Brassard, Hoyer, and Tapp, and imply an N^{3/4} log(N) quantum upper bound for the element distinctness problem (contrasting with N\\log(N) classical complexity). We also give an algorithm to finding a triangle in a graph more efficiently than classically.
Identification and distribution of intact polar branched tetraether lipids in peat and soil
Peterse, F.; Hopmans, E. C.; Schouten, S.; Rijpstra, W.I.C.; Sinninghe Damsté, J. S.
2011-01-01
Branched glycerol dialkyl glycerol tetraether lipids (GDGTs) are membrane lipids of soil bacteria that occur ubiquitously in soil, but their occurrence as intact polar lipids (IPLs) has not been well studied. Here, we report the identification and distribution of IPL-branched GDGTs throughout a depth profile of a Swedish peat bog. In addition to two reported glycosidic IPL branched GDGTs, we identified IPL branched GDGTs with a hexose-glycuronic acid, phospho-hexose, or hexose-phosphoglycerol...
On Shrinking and Boundedly Complete Schauder Frames of Banach spaces
Liu, Rui
2009-01-01
This paper studies Schauder frames in Banach spaces, a concept which is a natural generalization of frames in Hilbert spaces and Schauder bases in Banach spaces. The associated minimal and maximal spaces are introduced, as are shrinking and boundedly complete Schauder frames. Our main results extend the classical duality theorems on bases to the situation of Schauder frames. In particular, we will generalize James' results on shrinking and boundedly complete bases to frames. Secondly we will ...
Balanced distribution-energy inequalities and related entropy bounds
Rumin, Michel
2010-01-01
Let $A$ be a self-adjoint operator acting over a space $X$ endowed with a partition. We give lower bounds on the energy of a mixed state $\\rho$ from its distribution in the partition and the spectral density of $A$. These bounds improve with the refinement of the partition, and generalize inequalities by Li-Yau and Lieb--Thirring for the Laplacian in $\\R^n$. They imply an uncertainty principle, giving a lower bound on the sum of the spatial entropy of $\\rho$, as seen from $X$, and some spectral entropy, with respect to its energy distribution. On $\\R^n$, this yields lower bounds on the sum of the entropy of the densities of $\\rho$ and its Fourier transform. A general log-Sobolev inequality is also shown. It holds on mixed states, without Markovian or positivity assumption on $A$.
US Forest Service Survey parcels described by metes and bounds
US Forest Service, Department of Agriculture — A map service on the www depicting survey parcels described by a metes and bounds description. Examples include: land lots, housing subdivision lots, mineral...
Bounded solutions for fuzzy differential and integral equations
Energy Technology Data Exchange (ETDEWEB)
Nieto, Juan J. [Departamento de Analisis Matematico Facultad de Matematicas Universidad de Santiago de Compostela, 15782 (Spain)] e-mail: amnieto@usc.es; Rodriguez-Lopez, Rosana [Departamento de Analisis Matematico Facultad de Matematicas Universidad de Santiago de Compostela, 15782 (Spain)] e-mail: amrosana@usc.es
2006-03-01
We find sufficient conditions for the boundness of every solution of first-order fuzzy differential equations as well as certain fuzzy integral equations. Our results are based on several theorems concerning crisp differential and integral inequalities.
Zhou, Hui; Kunz, Thomas; Schwartz, Howard
2011-01-01
Traditional oscillators used in timing modules of CDMA and WiMAX base stations are large and expensive. Applying cheaper and smaller, albeit more inaccurate, oscillators in timing modules is an interesting research challenge. An adaptive control algorithm is presented to enhance the oscillators to meet the requirements of base stations during holdover mode. An oscillator frequency stability model is developed for the adaptive control algorithm. This model takes into account the control loop which creates the correction signal when the timing module is in locked mode. A recursive prediction error method is used to identify the system model parameters. Simulation results show that an oscillator enhanced by our adaptive control algorithm improves the oscillator performance significantly, compared with uncorrected oscillators. Our results also show the benefit of explicitly modeling the control loop. Finally, the cumulative time error upper bound of such enhanced oscillators is investigated analytically and comparison results between the analytical and simulated upper bound are provided. The results show that the analytical upper bound can serve as a practical guide for system designers. PMID:21244973
DEFF Research Database (Denmark)
Rasmussen, Marie-Louise Højlund; Stolpe, Mathias
2008-01-01
physics, and the cuts (Combinatorial Benders’ and projected Chvátal–Gomory) come from an understanding of the particular mathematical structure of the reformulation. The impact of a stronger representation is investigated on several truss topology optimization problems in two and three dimensions.......The subject of this article is solving discrete truss topology optimization problems with local stress and displacement constraints to global optimum. We consider a formulation based on the Simultaneous ANalysis and Design (SAND) approach. This intrinsically non-convex problem is reformulated to a...... mixed-integer linear program, which is solved with a parallel implementation of branch-and-bound. Additional valid inequalities and cuts are introduced to give a stronger representation of the problem, which improves convergence and speed up of the parallel method. The valid inequalities represent the...
'Lion and man' : upper and lower bounds
Alonso, Laurent; Goldstein, Arthur S.; Reingold, Edward M.
1992-01-01
Given a lion and a man, their initial position, and restrictions on their ranges and speeds, how quickly can the lion get within a given distance from the man? We consider the case in which the lion and man are restricted to the interior of a circle and each is limited to the same speed
Quantifying Bounded Rationality: Managerial Behaviour and the Smith Predictor
Riddalls, C.E.; Bennett, S.
2001-01-01
The concept of bounded rationality in decision making and research on its relegation to aggregate system dynamics is examined. By recasting one such example of a dynamic system, the Beer Game, as a Smith predictor control system is derived. A stability analysis is then employed to support the and qualify the assertion that the level of bounded rationality can adversely affect the aggregate dynamic behaviour of such supply chains. The analytical basis of these calculations enables the qualific...
Higgs interchange and bound states of superheavy fermions
Indian Academy of Sciences (India)
M De Sanctis
2013-09-01
Hypothetical superheavy fourth-generation fermions with a very small coupling with the rest of the Standard Model can give rise to long enough lived bound states. The production and the detection of these bound states would be experimentally feasible at the LHC. Extending, in the present study, the analysis of other authors, a semirelativistic wave equation is solved using an accurate numerical method to determine the binding energies of these possible superheavy fermion-bound states. The interaction given by the Yukawa potential of the Higgs boson exchange is considered; the corresponding relativistic corrections are calculated by means of a model based on the covariance properties of the Hamiltonian. We study the effects given by the Coulomb force. Moreover, we calculate the contributions given by the Coulombic and confining terms of the strong interaction in the case of superheavy quark bound states. The results of the model are critically analysed.
Alternation-Trading Proofs, Linear Programming, and Lower Bounds
Williams, Ryan
2010-01-01
A fertile area of recent research has demonstrated concrete polynomial time lower bounds for solving natural hard problems on restricted computational models. Among these problems are Satisfiability, Vertex Cover, Hamilton Path, Mod6-SAT, Majority-of-Majority-SAT, and Tautologies, to name a few. The proofs of these lower bounds follow a certain proof-by-contradiction strategy that we call alternation-trading. An important open problem is to determine how powerful such proofs can possibly be. We propose a methodology for studying these proofs that makes them amenable to both formal analysis and automated theorem proving. We prove that the search for better lower bounds can often be turned into a problem of solving a large series of linear programming instances. Implementing a small-scale theorem prover based on this result, we extract new human-readable time lower bounds for several problems. This framework can also be used to prove concrete limitations on the current techniques.
Cosmological stability bound in massive gravity and bigravity
International Nuclear Information System (INIS)
We give a simple derivation of a cosmological bound on the graviton mass for spatially flat FRW solutions in massive gravity with an FRW reference metric and for bigravity theories. This bound comes from the requirement that the kinetic term of the helicity zero mode of the graviton is positive definite. The bound is dependent only on the parameters in the massive gravity potential and the Hubble expansion rate for the two metrics. We derive the decoupling limit of bigravity and FRW massive gravity, and use this to give an independent derivation of the cosmological bound. We recover our previous results that the tension between satisfying the Friedmann equation and the cosmological bound is sufficient to rule out all observationally relevant FRW solutions for massive gravity with an FRW reference metric. In contrast, in bigravity this tension is resolved due to different nature of the Vainshtein mechanism. We find that in bigravity theories there exists an FRW solution with late-time self-acceleration for which the kinetic terms for the helicity-2, helicity-1 and helicity-0 are generically nonzero and positive making this a compelling candidate for a model of cosmic acceleration. We confirm that the generalized bound is saturated for the candidate partially massless (bi)gravity theories but the existence of helicity-1/helicity-0 interactions implies the absence of the conjectured partially massless symmetry for both massive gravity and bigravity
Tau reconstruction and identification algorithm
Indian Academy of Sciences (India)
Raman Khurana
2012-11-01
CMS has developed sophisticated tau identification algorithms for tau hadronic decay modes. Production of tau lepton decaying to hadrons are studied at 7 TeV centre-of-mass energy with 2011 collision data collected by CMS detector and has been used to measure the performance of tau identification algorithms by measuring identification efficiency and misidentification rates from electrons, muons and hadronic jets. These algorithms enable extended reach for the searches for MSSM Higgs, and other exotic particles.
The Laplace Functional and Moments for Markov Branching Chains in Random Environments
Institute of Scientific and Technical Information of China (English)
HU Di-he; ZHANG Shu-lin
2005-01-01
The concepts of random Markov matrix, Markov branching chain in random environment (MBCRE) and Laplace functional of Markov branching chain in random environment (LFMBCRE) are introduced. The properties of LFMBCRE and the explicit formulas of moments of MBCRE are given.
Bounds for Regularity and Coregularity of Graded Modules
Indian Academy of Sciences (India)
Reza Sazeedeh
2007-11-01
Let be a finitely generated graded module over a Noetherian homogeneous ring with local base ring $(R_0,\\mathfrak{m}_0)$. If 0 is of dimension one, then we show that $\\mathrm{reg}^i+1(M)$ and $\\mathrm{coreg}^{i+1}(M)$ are bounded for all $i\\in\\mathbb{N}_0$. We improve these bounds, if in addition, 0 is either regular or analytically irreducible of unequal characteristic.
Query-Number Preserving Reductions and Linear Lower Bounds for Testing
Yoshida, Yuichi; Ito, Hiro
In this paper, we study lower bounds on the query complexity of testing algorithms for various problems. Given an oracle that returns information of an input object, a testing algorithm distinguishes the case that the object has a given property P from the case that it has a large distance to having P with probability at least 2/3. The query complexity of an algorithm is measured by the number of accesses to the oracle. We introduce two reductions that preserve the query complexity. One is derived from the gap-preserving local reduction and the other is from the L-reduction. By using the former reduction, we show linear lower bounds on the query complexity for testing basic NP-complete properties, i.e., 3-edge-colorability, directed Hamiltonian path/cycle, undirected Hamiltonian path/cycle, 3-dimensional matching and NP-complete generalized satisfiability problems. Also, using the second reduction, we show a linear lower bound on the query complexity of approximating the size of the maximum 3-dimensional matching.
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
Biswal, Punyashloka; Rao, Satish
2008-01-01
We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the Rayleigh quotient. Using this, we show that every $n$-vertex graph of genus $g$ and maximum degree $d$ satisfies $\\lambda_2(G) = O((g+1)^3 d/n)$. This recovers the $O(d/n)$ bound of Spielman and Teng for planar graphs, and compares to Kelner's bound of $O((g+1) poly(d)/n)$, but our proof does not make use of conformal mappings or circle packings. We are thus able to extend this to resolve positively a conjecture of Spielman and Teng, by proving that $\\lambda_2(G) = O(d h^6 \\log h/n)$ whenever $G$ is $K_h$-minor free. This shows, in particular, that spectral partitioning can be used to recover $O(\\sqrt{n})$-sized separators in bounded degree graphs that exclude a fixed minor. We extend this further by obtaining nearly optimal bounds on $\\lambda_2$ for graphs which exc...
Hybridizing multi-inver-over evolutionary algorithms with tabu search for the symmetric TSP
Bermúdez, Carlos; Minetti, Gabriela F.; Alfonso, Hugo; Gallard, Raúl Hector
2001-01-01
The travelling salesman problem (TSP) is a NP-hard problem. Techniques as either Branch and Bound or Dynamic Programming supplied the global optimum solution for instances with more than 7000 cities. But, ther needed more than 4 years of CPU time. Fortunately, faster algorithms (simulated annealing, tabu search, neural networks, and evolutionary computation) exist although they do not guarantee to find the global optimum. Recently an EA based on a operator inver-over [4], provides optimal ...
ULNAR NERVE, ITS TERMINATION AND SUPERFICIAL BRANCHES IN HAND: A CADAVERIC STUDY
Directory of Open Access Journals (Sweden)
A Priyadarshini
2015-12-01
Full Text Available Introduction: Nerves supplying the hand are notoriously variable in their divisions and their course; do not follow any standard pattern. The palmar aspect of hand is supplied by median and ulnar nerve. The clinical importance of Guyon's canal is emphasized due to the various branching patterns of the ulnar nerve in this canal. The palmar aspect of hand is usually supplied by ulnar nerve and median nerve. Medial one and a half fingers are supplied by ulnar nerve and lateral three and a half fingers are supplied by the median nerve. The branches of ulnar nerve are notoriously variable morphologically and no standard pattern can be given regarding the course of these branches. Presence of trifurcation of ulnar nerve or communications of superficial branches to median nerve do not cause symptoms usually but becomes important during surgical and orthopaedic interventions. Material and Methods: The study was conducted on 40 hands (20 left and 20 right of preserved adult human cadavers.The roof of the Guyon's canal was opened with care not to disturb the stuctures. The ulnar nerve observed for its terminal branches, the course of its superficial branches was observed. The point of division of superficial branch into digital branches was measured from bistyloid line. The point of origin of superficial communicating branch from superficial branch or digital branch of ulnar nerve to median nerve was observed from bistyloid line. Observations: In 29 hands the ulnar nerve showed bifurcation, in 10 hands it trifurcated in the Guyon's canal and in 1 right hand of a male cadaver there was higher division of the ulnar nerve and trifurcation.The superficial branch was observed for its course and division from bistyloid line. The superficial branch gave rise to 2 digital branches in 27 hands and it gave 3 branches i.e. 2 digital branches and 1 communicating branch to medialmost digital branch of median nerve in 13 hands. The typical ramus communicans from
Nature and Properties of a Repulsive Fermi Gas in the Upper Branch of the Energy Spectrum
International Nuclear Information System (INIS)
We generalize the Nozieres-Schmitt-Rink method to study the repulsive Fermi gas in the absence of molecule formation, i.e., in the so-called ''upper branch.'' We find that the system remains stable except close to resonance at sufficiently low temperatures. With increasing scattering length, the energy density of the system attains a maximum at a positive scattering length before resonance. This is shown to arise from Pauli blocking which causes the bound states of fermion pairs of different momenta to disappear at different scattering lengths. At the point of maximum energy, the compressibility of the system is substantially reduced, leading to a sizable uniform density core in a trapped gas. The change in spin susceptibility with increasing scattering length is moderate and does not indicate any magnetic instability. These features should also manifest in Fermi gases with unequal masses and/or spin populations.
Research on Power Line as Communication Channel with Multi-Tap and Multi-Branch Configuration
Directory of Open Access Journals (Sweden)
Yanhua Zheng
2013-12-01
Full Text Available To study the effect of different branch configuration on transmission characteristic in-home low-voltage (LV communication power line communication (PLC channel, the influences of branch length, number of branch and tap, and branch terminal impedance on the performance of PLC are investigated. The two type power line network structures of the one-tap with multi-branch (OTMB and the multi-tap with multi-branch (MTMB are studied. The transmission characteristics of the PLC channel are simulated by varying the length and terminal impedance of the branch for two configurations. Simulation results show that the length and terminal impedance of the branch have significant influence on the amplitude and phase response of the transfer function. The position and number of notches and crests in the amplitude responses are affected by different branch types and the configurations of branch length and branch terminal impedance. The models developed in this paper can easily handle an arbitrary topology of power line channel and provide accurate calculation for the channel responses of the all kinds of channel branch structures in indoor LV power line network
Flory approximation for directed branched polymers and directed percolation
Lubensky, T. C.; Vannimenus, J.
1982-01-01
The Flory approximation for the radius of gyration of dilute polymers is generalized to systems with a preferred direction. The mean radius then increases with their size N as Nν∥ in the preferred direction and as Nν〉 in the transverse directions. In the case of directed branched polymers (lattice animals) and of directed percolation, the upper critical dimension dc is predicted correctly, and the values obtained by ν∥ and ν 〉 are in very good agreement with the values from other methods in d...
Branching Shoots and Spikes from Lateral Meristems in Bread Wheat
Wang, Ying; Miao, Fang; Yan, Liuling
2016-01-01
Wheat grain yield consists of three components: spikes per plant, grains per spike (i.e. head or ear), and grain weight; and the grains per spike can be dissected into two subcomponents: spikelets per spike and grains per spikelet. An increase in any of these components will directly contribute to grain yield. Wheat morphology biology tells that a wheat plant has no lateral meristem that forms any branching shoot or spike. In this study, we report two novel shoot and spike traits that were pr...
THE EXISTENCE AND MOMENTS OF CANONICAL BRANCHING CHAIN IN RANDOM ENVIRONMENT
Institute of Scientific and Technical Information of China (English)
胡迪鹤
2004-01-01
The concepts of branching chain in random environmnet and canonical branching chain in random environment axe introduced. Moreover the existence of these chains is proved. Finally the exact formulas of mathematical expectation and variance of branching chain in random environment axe also given.
Weber, Y.; De Jonge, C.; Rijpstra, W.I.C.; Hopmans, E. C.; Stadnitskaia, A.; Schubert, C J; Lehmann, M.F.; Sinninghe Damsté, J. S.; Niemann, H.
2015-01-01
Branched glycerol dialkyl glycerol tetraethers (brGDGTs) are bacterial membrane lipids that occur ubiquitously in soils and lacustrine sediments and have great potential as proxy indicators for paleotemperature and pH reconstructions. Initially, brGDGTs in lakes were thought to originate from soils of the watershed. The composition of the lacustrine brGDGT pool, however, often differs substantially from that in catchment soils, complicating the application of the brGDGT paleothermometer to la...
DEFF Research Database (Denmark)
Achtziger, Wolfgang; Stolpe, Mathias
2009-01-01
we use the theory developed in Part I to design a convergent nonlinear branch-and-bound method tailored to solve large-scale instances of the original discrete problem. The problem formulation and the needed theoretical results from Part I are repeated such that this paper is self-contained. We focus...... on the implementation details but also establish finite convergence of the branch-and-bound method. The algorithm is based on solving a sequence of continuous non-convex relaxations which can be formulated as quadratic programs according to the theory in Part I. The quadratic programs to be treated...... within the branch-and-bound search all have the same feasible set and differ from each other only in the objective function. This is one reason for making the resulting branch-and-bound method very efficient. The paper closes with several large-scale numerical examples. These examples are, to the...
Capacity Bounds for Parallel Optical Wireless Channels
Chaaban, Anas
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.
Lattice magnetic analog of branched polymers, lattice animals and percolation
González, A E
1985-01-01
It is shown that the n = 0 limit of a magnetic system consisting of nq-component spins on a lattice, interacting with multibody forces and with an external magnetic field coupled to the first q components, gives us a correspondence with a system of branched polymers in a good solvent For certain specific values of the fugacities, a lattice animal point and a « quasi-percolation » point (in which only the exponents αP and νP can be extracted) are obtained.
Public Relations as Scientific Branch of Information and Communication Sciences
Directory of Open Access Journals (Sweden)
Hrvoje Jakopović
2012-06-01
Full Text Available Given that the field of information and communication sciences is a young field in the social sciences, it is important to consider how technology impacts the development of this field. This is especially relevant when looking at the area of public relations. Amid changing technological developments public relations is constantly being redefined in this complex environment. This work focuses on the development of public relations as a branch of study in the field of information and communication sciences. I review the scientific methods used to evaluate the influence and effects of public relations, while discussing the different methodological approaches.
Optimized Ultrawideband and Uniplanar Minkowski Fractal Branch Line Coupler
Directory of Open Access Journals (Sweden)
Mohammad Jahanbakht
2012-01-01
Full Text Available The non-Euclidean Minkowski fractal geometry is used in design, optimization, and fabrication of an ultrawideband (UWB branch line coupler. Self-similarities of the fractal geometries make them act like an infinite length in a finite area. This property creates a smaller design with broader bandwidth. The designed 3 dB microstrip coupler has a single layer and uniplanar platform with quite easy fabrication process. This optimized 180° coupler also shows a perfect isolation and insertion loss over the UWB frequency range of 3.1–10.6 GHz.
Characterization of linear and branched polyacrylates by tandem mass spectrometry.
Chaicharoen, Kittisak; Polce, Michael J; Singh, Anirudha; Pugh, Coleen; Wesdemiotis, Chrys
2008-10-01
The unimolecular degradation of alkali-metal cationized polyacrylates with the repeat unit CH(2)CH(COOR) and a variety of ester pendants has been examined by tandem mass spectrometry. The fragmentation patterns resulting from collisionally activated dissociation depend sensitively on the size of the ester alkyl substituent (R). With small alkyl groups, as in poly(methyl acrylate), lithiated or sodiated oligomers (M) decompose via free-radical chemistry, initiated by random homolytic C-C bond cleavages along the polymer chain. The radical ions formed this way dissociate further by backbiting rearrangements and beta scissions to yield a distribution of terminal fragments with one of the original end groups and internal fragments with 2-3 repeat units. If the ester alkyl group bears three or more carbon atoms, cleavages within the ester moieties become the predominant decomposition channel. This distinct reactivity is observed if R = t-butyl, n-butyl, or the mesogenic group (CH(2))(11)-O-C(6)H(4)-C(6)H(4)-CN. The [M+alkali metal](+) ions of the latter polyacrylates dissociate largely by charge-remote 1,5-H rearrangements that convert COOR to COOH groups by expulsion of 1-alkenes. The acid groups may displace an alcohol unit from a neighboring ester pendant to form a cyclic anhydride, unless hindered by steric effects. Using atom transfer radical polymerization, hyperbranched polyacrylates were prepared carrying ester groups both within and between the branches. Unique alkenes and alcohols are cleaved from ester groups at the branching points, enabling determination of the branching architecture. PMID:18373231
Direct Heuristic Algorithm for Linear Programming
Directory of Open Access Journals (Sweden)
I. Ramesh Babu
2013-08-01
Full Text Available Many applications in business and economics involve a process called optimization, in which we will be required to find the minimum cost, the maximum profit, or the minimum use of resources, where a decision maker may want to utilize limited available resources in the best possible manner. The limited resources may include material, money, manpower, space and time. Linear Programming provides various methods of solving such problems. The formulation of linear programming problem as a mathematical model is one type of optimization problem called linear programming. There are various methods for solving the linear programming problems. Some of them are approximation algorithm , branch and bound methods, cutting plane method etc. Other than Gomory’s cutting plane method, Branch and bound method LPP along with the DHALP (Direct heuristic algorithm for linear programming algorithm which is more efficient than these existing methods will be used for solving linear programming problems. An optimality test will also be included in this. Numerical experiments will depict the utility/scope of such a procedure.
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.
Third annual Walker Branch watershed research symposium: Programs and abstracts
International Nuclear Information System (INIS)
The methods and concepts of watershed research, originally applied in an experimental or monitoring mode to relatively small catchments, are increasingly being used at larger scales and for specific applied problems. Research at Oak Ridge National Laboratory, the Tennessee Valley Authority, the US Forest Service, and other agencies and institutions participating in this symposium reflects research over a broad range of spatial scales. These research projects address the basic atmospheric, geophysical, biogeochemical, and biological processes that regulate the responses of forested ecosystems to natural environmental variation and anthropogenic stresses. Regional and global issues addressed by presentations include emissions of carbon dioxide, methane, and other hydrocarbons; deposition of sulfate, nitrate, and mercury; land-use changes; biological diversity; droughts; and water quality. The Department of Energy's local research site, Walker Branch Watershed, is a long-term ecosystem research project initiated on the Oak Ridge Reservation in 1967. Walker Branch provides a well-characterized site where many of these methods can be tested and applied.In addition, other large-scale experiments represented in this symposium include experiments on the effects of clearcutting and burning on forest structure and productivity associated with Coweeta Hydrologic Laboratory, and whole-tree ozone exposure chambers constructed by TVA and ORNL researchers
Lifetimes, branching ratios, and transition probabilities in Co ii
Salih, S.; Lawler, J. E.; Whaling, W.
1985-01-01
The radiative lifetime of 14 levels in the z^5F, z^5D, and z^5G terms of Co ii have been measured with use of time-resolved laser fluorescence spectroscopy with a Co+-ion beam. Our lifetime values are shorter by 15–50 % than earlier results from beam-foil time-of-flight measurements. The lifetimes were converted to 41 individual transition probabilities with use of branching ratios measured on spectra recorded with the 1-m Fourier-transform spectrometer at the Kitt Peak National Observatory. ...
March dl: Adding Adaptive Heuristics and a New Branching Strategy
Marijn J.H. Heule; Hans van Maaren
2006-01-01
We introduce the march dl satisfiability (SAT) solver, a successor of march eq. The latter was awarded state-of-the-art in two categories during the Sat 2004 competition. The focus lies on presenting those features that are new in march dl. Besides a description, each of these features is illustrated with some experimental results. By extending the pre-processor, using adaptive heuristics, and by using a new branching strategy, march dl is able to solve nearly all benchmarks faster than its ...
March dl: Adding Adaptive Heuristics and a New Branching Strategy
Directory of Open Access Journals (Sweden)
Marijn J.H. Heule
2006-03-01
Full Text Available We introduce the march dl satisfiability (SAT solver, a successor of march eq. The latter was awarded state-of-the-art in two categories during the Sat 2004 competition. The focus lies on presenting those features that are new in march dl. Besides a description, each of these features is illustrated with some experimental results. By extending the pre-processor, using adaptive heuristics, and by using a new branching strategy, march dl is able to solve nearly all benchmarks faster than its predecessor. Moreover, various instances which were beyond the reach of march eq, can now be solved - relatively easily - due to these new features.
Yu, Wenfei
2007-04-01
The observations of the bright persistent neutron star low-mass X-ray binary (LMXB) Sco X-1 performed with the Rossi X-Ray Timing Explorer (RXTE) show a ~6 Hz normal-branch oscillation (NBO), a ~45 Hz horizontal-branch oscillation (HBO), and twin kilohertz quasi-periodic oscillations (kHz QPOs) on its normal branch simultaneously. We have found that the fractional amplitude of the HBO corresponding to the NBO phase of high flux is 1.1%, while that of the NBO phase of low flux is undetectable, with a 3 σ upper limit of 0.4%, implying that the HBO strength varies with the NBO phase in a manner opposite that of the lower kHz QPO previously found, and suggests that the condition for the generation of the HBO is met when the NBO flux is high. The 6 Hz NBO in Sco X-1 connects the 45 Hz HBO and the twin kHz QPO together, showing a unique picture indicating a coupling between the QPOs, which has never been observed in other neutron star LMXBs. We discuss the implications for current models of the 45 Hz HBO, the 6 Hz NBO, and the twin kHz QPOs.