GYutsis: heuristic based calculation of general recoupling coefficients

General angular momentum recoupling coefficients can be expressed as a summation formula over products of 6-j coefficients. Yutsis, Levinson and Vanagas developed graphical techniques for representing the general recoupling coefficient as a cubic graph and they describe a set of reduction rules allowing a stepwise generation of the corresponding summation formula. This paper is a follow up to [Van Dyck and Fack, Comput. Phys. Comm. 151 (2003) 353-368] where we described a heuristic algorithm based on these techniques. In this article we separate the heuristic from the algorithm and describe some new heuristic approaches which can be plugged into the generic algorithm. We show that these new heuristics lead to good results: in many cases we get a more efficient summation formula than our previous approach, in particular for problems of higher order. In addition the new features and the use of our program GYutsis, which implements these techniques, is described both for end users and application programmers.

Program summary

Title of program: CycleCostAlgorithm, GYutsisCatalogue number: ADSAProgram Summary URL:http://cpc.cs.qub.ac.uk/summaries/ADSAProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. Ireland. Users may obtain the program also by downloading either the compressed tar file gyutsis.tgz (for Unix and Linux) or the zip file gyutsis.zip (for Windows) from our website (http://caagt.rug.ac.be/yutsis/). An applet version of the program is also available on our website and can be run in a web browser from the URL http://caagt.rug.ac.be/yutsis/GYutsisApplet.html.Licensing provisions: noneComputers for which the program is designed: any computer with Sun's Java Runtime Environment 1.4 or higher installed.Programming language used: Java 1.2 (Compiler: Sun's SDK 1.4.0)No. of lines in program: approximately 9400No. of bytes in distributed program, including test data, etc.: 544 117Distribution format: tar gzip fileNature of physical problem: A general recoupling coefficient for an arbitrary number of (integer or half-integer) angular momenta can be expressed as a formula consisting of products of 6-j coefficients summed over a certain number of variables. Such a formula can be generated using the program GYutsis (with a graphical user front end) or CycleCostAlgorithm (with a text-mode user front end).Method of solution: Using the graphical techniques of Yutsis, Levinson and Vanagas (1962) a summation formula for a general recoupling coefficient is obtained by representing the coefficient as a Yutsis graph and by performing a selection of reduction rules valid for such graphs. Each reduction rule contributes to the final summation formula by a numerical factor or by an additional summation variable. Whereas an optimal summation formula (i.e. with a minimum number of summation variables) is hard to obtain, we present here some new heuristic approaches for selecting an edge from a k-cycle in order to transform it into an (k−1)-cycle (k>3) in such a way that a ‘good’ summation formula is obtained.Typical running time: From instantaneously for the typical problems to 30 s for the heaviest problems on a Pentium II-350 Linux-system with 256 MB RAM.     

New efficient programs to calculate general recoupling coefficients: Part I: Generation of a summation formula

A program to generate a summation formula in terms of 6-j coefficients for a general angular momentum recoupling coefficient is described. This algorithms makes use of binary tree transformations as introduced by Burke [Comput. Phys. Commun. 1 (1970) 241] in the program NJSYM. Due attention is paid to finding an optimal summation formula with a minimal number of summation variables, thereby improving the results of NJSYM. The results obtained here are at least as good as (and often better than) the results of the alternative approach NJGRAF, introduced by Bar-Shalom and Klapisch [Comput. Phys. Commun. 50 (1998) 375], using more advanced graphical methods.     

Improving vector space embedding of graphs through feature selection algorithms

Graph based pattern representation offers a versatile alternative to vectorial data structures. Therefore, a growing interest in graphs can be observed in various fields. However, a serious limitation in the use of graphs is the lack of elementary mathematical operations in the graph domain, actually required in many pattern recognition algorithms. In order to overcome this limitation, the present paper proposes an embedding of a given graph population in a vector space Rⁿ. The key idea of this embedding approach is to interpret the distances of a graph g to a number of prototype graphs as numerical features of g. In previous works, the prototypes were selected beforehand with heuristic selection algorithms. In the present paper we take a more fundamental approach and regard the problem of prototype selection as a feature selection or dimensionality reduction problem, for which many methods are available. With several experiments we show the feasibility of graph embedding based on prototypes obtained from such feature selection algorithms and demonstrate their potential to outperform previous approaches.     

A new weighted pathfinding algorithms to reduce the search time on grid maps

Artificial Intelligence (AI) techniques are utilized widely in the field of Expert Systems (ES) - as applied to robotics, video games self-driving vehicles and so on. Pathfinding algorithms are a class of heuristic algorithms based on AI techniques which are used in ES as decision making functions for the purpose of solving problems that would otherwise require human competence or expertise. ES fields that use pathfinding algorithms and operate in real-time face many challenges: for example time constraints, optimality and memory overhead for storing the paths which are found. For these algorithms to work, appropriate problem-specific maps must be constructed. In relation to this, the uniform-cost grid set-up is the most appropriate for ES applications. In this method, each node in a graph is represented as a tile, and the weight “between” tiles is set at a constant value, usually this is set to 1. In the state-of-the-art heuristic algorithms used with this data structure, multiplying the heuristic function by a weight greater than one is well-known technique. In this paper, we present three new techniques using various weights to accelerate heuristic search of grid maps. The first such technique is based on the iteration of a heuristic search algorithm associated with weight-set w. The second technique is based on the length between the start node and goal node, which is then associated with w. The last technique is based on the travel cost and is associated with a weight-set α. These techniques are applicable to a wide class of heuristic search algorithms. Therefore, we implement them, here, within the A*, the Bidirectional A* (Bi-A*) and Jump Point Search (JPS) algorithms; thus obtaining a family of new algorithms. Furthermore, it is seen that the use of these new algorithms results in significant improvements over current search algorithms. We evaluate them in path-planning benchmarks and show the amended JPS technique's greater stability, across weight values, over the other two techniques. However, it is also shown that this technique yields poor results in terms of cost solution.     

Good triangulations yield good tours

Consider the following heuristic for planar Euclidean instances of the traveling salesman problem (TSP): select a subset of the edges which induces a planar graph, and solve either the TSP or its graphical relaxation on that graph. In this paper, we give several motivations for considering this heuristic, along with extensive computational results. It turns out that the Delaunay and greedy triangulations make effective choices for the induced planar graph. Indeed, our experiments show that the resulting tours are on average within 0.1% of optimality.     

On labeling in graph visualization

When visualizing graphs, it is essential to communicate the meaning of each graph object via text or graphical labels. Automatic placement of labels in a graph is an NP-Hard problem, for which efficient heuristic solutions have been recently developed. In this paper, we describe a general framework for modeling, drawing, editing, and automatic placement of labels respecting user constraints. In addition, we present the interface and the basic engine of the Graph Editor Toolkit - a family of portable graph visualization libraries designed for integration into graphical user interface application programs. This toolkit produces a high quality automated placement of labels in a graph using our framework. A brief survey of automatic label placement algorithms is also presented. Finally we describe extensions to certain existing automatic label placement algorithms, allowing their integration into this visualization tool.     

A heuristic algorithm based on Monte Carlo methods for the Rural Postman Problem

In Routing Problems the aim is to determine a minimum cost traversal over a graph satisfying some specified constraints. Most of them are NP-hard problems and many different heuristic solution algorithms have been proposed. The name Monte Carlo, MC, applies to a set of heuristic procedures with the common feature of using random numbers to simulate a given process. MC approach has not been applied to the framework of Routing Problems in the literature. The purpose of this paper is to demonstrate that MC methods could be useful in implementing heuristic algorithms for Routing Problems. In particular, we design an efficient MC heuristic algorithm for the well known Rural Postman Problem (RPP), for which we have a set of instances with known optimal solution taken from the literature.The Rural Postman Problem (RPP) consists of finding a minimum cost traversal of a specified arc subset of a graph. Given that the RPP is a NP-hard problem, heuristic algorithms are interesting both to handle large size instances and to provide upper bounds that could be used in branch and cut procedures. In this paper we propose a heuristic algorithm for the RPP based on Monte Carlo methods. We simulate a vehicle travelling randomly over the graph, jumping from one node to another on the basis of certain probabilities. Monte Carlo methods provide a simple approach to many different Routing Problems and they are easily implemented in a computer code. The application of this algorithm to a set of RPP instances taken from the literature demonstrates that, using the appropriate probabilities, they are also efficient.     

A graph theoretical approach to determine a join reducer sequencein distributed query processing

Semijoin has traditionally been relied upon to reduce the cost of data transmission for distributed query processing. However, judiciously applying join operations as reducers can lead to further reduction in the amount of data transmission required. In view of this fact, we explore the approach of using join operations as reducers in distributed query processing. We first show that the problem of determining a sequence of join operations for a query can be transformed to that of finding a specific type of set of cuts to the corresponding query graph, where a cut to a graph is a partition of nodes in that graph. Then, in light of this concept, we prove that the problem of determining the optimal sequence of join operations for a given query graph is of exponential complexity, thus justifying the necessity of applying heuristic approaches to solve this problem. By mapping the problem of determining a sequence of join reducers into the one of finding a set of cuts, we develop (for tree and general query graphs, respectively) efficient heuristic algorithms to determine a join reducer sequence for distributed query processing. The algorithms developed are based on the concept of divide and conquer and are of polynomial time complexity. Simulation is performed to evaluate these algorithms     

Optimal network locality in distributed virtualized data-centers

Cost efficiency is a key aspect in deploying distributed service in networks within decentralized service delivery architectures. In this paper, we address this aspect from an optimization and algorithmic standpoint. The research deals with the placement of service components to network sites, where the performance metric is the cost for acquiring components between the sites. The resulting optimization problem, which we refer to as the k-Component Multi-site Placement Problem, is applicable to service distribution in a wide range of communication networking scenarios. We provide a theoretical analysis of the problem’s computational complexity, and develop an integer programming model for providing reference results for performance benchmarking. On the algorithmic side, we present four approaches: an algorithm with approximation guarantee and three heuristics algorithms. The first heuristic is derived from graph theory on domatic partition. The second heuristic, built on intuition, admits distributed computation. The third heuristic emphasizes on fairness in cost distribution among the sites. We report simulation results for sets of networks where cost is represented by round-trip time (RTT) originating from real measurements. For small networks, the integer model is used to study algorithm performance in terms of optimality. Large networks are used to compare the algorithms relatively to each other. Among the algorithms, the heuristic based on intuition has close-to-optimal performance, and the fairness heuristic achieves a good balance between single-site cost and the overall one. In addition, the experiments demonstrate the significance of optimization for cost reduction in comparison to a the random allocation strategy.     

Improving probabilistic inference in graphical models with determinism and cycles

Many important real-world applications of machine learning, statistical physics, constraint programming and information theory can be formulated using graphical models that involve determinism and cycles. Accurate and efficient inference and training of such graphical models remains a key challenge. Markov logic networks (MLNs) have recently emerged as a popular framework for expressing a number of problems which exhibit these properties. While loopy belief propagation (LBP) can be an effective solution in some cases; unfortunately, when both determinism and cycles are present, LBP frequently fails to converge or converges to inaccurate results. As such, sampling based algorithms have been found to be more effective and are more popular for general inference tasks in MLNs. In this paper, we introduce Generalized arc-consistency Expectation Maximization Message-Passing (GEM-MP), a novel message-passing approach to inference in an extended factor graph that combines constraint programming techniques with variational methods. We focus our experiments on Markov logic and Ising models but the method is applicable to graphical models in general. In contrast to LBP, GEM-MP formulates the message-passing structure as steps of variational expectation maximization. Moreover, in the algorithm we leverage the local structures in the factor graph by using generalized arc consistency when performing a variational mean-field approximation. Thus each such update increases a lower bound on the model evidence. Our experiments on Ising grids, entity resolution and link prediction problems demonstrate the accuracy and convergence of GEM-MP over existing state-of-the-art inference algorithms such as MC-SAT, LBP, and Gibbs sampling, as well as convergent message passing algorithms such as the concave–convex procedure, residual BP, and the L2-convex method.     

Memory intensive AND/OR search for combinatorial optimization in graphical models

In this paper we explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation (MPE) in belief networks and solving Weighted CSPs (WCSP). In an extensive empirical evaluation we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks.     

Efficient Rate-Distortion Optimized Media Streaming for Tree-Structured Packet Dependencies

When streaming packetized media data over a lossy packet network, it is desirable to use transmission strategies that minimize the expected distortion subject to a constraint on the expected transmission rate. Because the computation of such optimal strategies is usually an intractable problem, fast heuristic techniques are often used. We first show that when the graph that gives the decoding dependencies between the data packets is reducible to a tree, optimal transmission strategies can be efficiently computed with dynamic programming algorithms. The proposed algorithms are much faster than other exact algorithms developed for arbitrary dependency graphs. They are slower than previous heuristic techniques but can provide much better solutions. We also show how to apply our algorithms to find high-quality approximate solutions when the dependency graph is not tree reducible. To validate our approach, we run simulations for MPEG1 and H.264 video data. We first consider a simulated packet erasure channel. Then we implement a real video streaming system and provide experimental results for an Internet connection.     

Incremental <Emphasis Type="Italic">k</Emphasis>-core decomposition: algorithms and evaluation

A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, visualization, and solving NP-hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for dynamic graph data. In this paper, we propose a suite of incremental k-core decomposition algorithms for dynamic graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values have changed and efficiently process this subgraph to update the k-core decomposition. We present incremental algorithms for both insertion and deletion operations, and propose auxiliary vertex state maintenance techniques that can further accelerate these operations. Our results show a significant reduction in runtime compared to non-incremental alternatives. We illustrate the efficiency of our algorithms on different types of real and synthetic graphs, at varying scales. For a graph of 16 million vertices, we observe relative throughputs reaching a million times, relative to the non-incremental algorithms.     

On Two Techniques of Combining Branching and Treewidth

Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques. In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for Minimum Maximal Matching and for counting all 3-colorings of a graph. In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph. We also discuss how similar techniques can be used to design faster parameterized algorithms. A preliminary version of this paper appeared as Branching and Treewidth Based Exact Algorithms in the Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006) [15]. Additional support by the Research Council of Norway.     

The three-stage assembly flowshop scheduling problem

We consider the three-stage assembly flowshop scheduling problem with the objective of minimizing the makespan. The three-stage assembly problem generalizes both the serial three machine flowshop problem and the two-stage assembly flowshop scheduling problem and is therefore strongly NP-hard. We analyze the worst-case ratio bound for several heuristics for this problem. We also analyze the worst-case absolute bound for a heuristic based on compact vector summation techniques and we point out that, for a large number of jobs, this heuristic becomes asymptotically optimal.Scope and purposeThe three-stage assembly flowshop scheduling problem models situations which arise frequently in manufacturing when various fabrication operations are performed concurrently and then collected and transported into an assembly area for a final assembly operation. The main criterion for this problem is the minimization of the maximum job completion time (makespan). The objective of this paper is to derive algorithms for minimizing the makespan. In doing so, we also demonstrate the reduction of assembly flowshop problems to their embedded serial flowshop problems.     

Weighted heuristic anytime search: new schemes for optimization over graphical models

Weighted heuristic search (best-first or depth-first) refers to search with a heuristic function multiplied by a constant w [31]. The paper shows, for the first time, that for optimization queries in graphical models the weighted heuristic best-first and weighted heuristic depth-first branch and bound search schemes are competitive energy-minimization anytime optimization algorithms. Weighted heuristic best-first schemes were investigated for path-finding tasks. However, their potential for graphical models was ignored, possibly because of their memory costs and because the alternative depth-first branch and bound seemed very appropriate for bounded depth. The weighted heuristic depth-first search has not been studied for graphical models. We report on a significant empirical evaluation, demonstrating the potential of both weighted heuristic best-first search and weighted heuristic depth-first branch and bound algorithms as approximation anytime schemes (that have sub-optimality bounds) and compare against one of the best depth-first branch and bound solvers to date.     

Scheduling algorithms for PIPE (pipelined image-processing engine)

In this paper we present heuristic scheduling algorithms for the National Bureau of Standards/Aspen Inc. Pipelined Image-Processing Engine (PIPE). PIPE is a special-purpose machine for low-level image processing consisting of a linearly connected array of processing stages. A program is specified as a directed acyclic graph (DAG). Our first algorithm schedules planar DAGs. It works top-down through the graph and uses the greedy approach to schedule operations on a stage. It uses several heuristics to control the movement of images between stages. The worst case time for the schedule generated by the algorithm is O(N) times the optimal schedule, where N is the maximum width of the graph. We generalize this algorithm to work on nonplanar graphs, using heuristics for repositioning images on the stages of PIPE. The worst case time for the more general algorithm is also O(N) times the optimal schedule. Finally, we analyze the problem of optimizing throughput and latency for a sequence of DAGs on PIPE.     

Heuristic algorithms for scheduling iterative task computations ondistributed memory machines

Many partitioned scientific programs can be modeled as iterative executions of computational tasks and represented by iterative task graphs (ITGs). An ITG may or may not have dependence cycles. In this paper, we consider the symbolic scheduling of ITGs on distributed memory architectures with nonzero communication overhead and propose heuristic algorithms for scheduling both cyclic and acyclic ITGs without searching an entire iteration space. Our approach incorporates techniques of software pipelining, graph unfolding, directed acyclic graph (DAG) scheduling, and load balancing. We analyze the asymptotic optimality of the algorithms to show that the derived schedules are competitive to optimal solutions. We also study the sensitivity of scheduling performance on inaccurate weights. Finally, we present experimental results to demonstrate the effectiveness of the optimization techniques     

3D segmentation of abdominal CT imagery with graphical models,conditional random fields and learning

Probabilistic graphical models have had a tremendous impact in machine learning and approaches based on energy function minimization via techniques such as graph cuts are now widely used in image segmentation. However, the free parameters in energy function-based segmentation techniques are often set by hand or using heuristic techniques. In this paper, we explore parameter learning in detail. We show how probabilistic graphical models can be used for segmentation problems to illustrate Markov random fields (MRFs), their discriminative counterparts conditional random fields (CRFs) as well as kernel CRFs. We discuss the relationships between energy function formulations, MRFs, CRFs, hybrids based on graphical models and their relationships to key techniques for inference and learning. We then explore a series of novel 3D graphical models and present a series of detailed experiments comparing and contrasting different approaches for the complete volumetric segmentation of multiple organs within computed tomography imagery of the abdominal region. Further, we show how these modeling techniques can be combined with state of the art image features based on histograms of oriented gradients to increase segmentation performance. We explore a wide variety of modeling choices, discuss the importance and relationships between inference and learning techniques and present experiments using different levels of user interaction. We go on to explore a novel approach to the challenging and important problem of adrenal gland segmentation. We present a 3D CRF formulation and compare with a novel 3D sparse kernel CRF approach we call a relevance vector random field. The method yields state of the art performance and avoids the need to discretize or cluster input features. We believe our work is the first to provide quantitative comparisons between traditional MRFs with edge-modulated interaction potentials and CRFs for multi-organ abdominal segmentation and the first to explore the 3D adrenal gland segmentation problem. Finally, along with this paper we provide the labeled data used for our experiments to the community.