Depth-m search in branch-and-bound algorithms

A new search strategy, called depth-m search, is proposed for branch-and-bound algorithms, wherem is a parameter to be set by the user. In particular, depth-1 search is equivalent to the conventional depth-first search, and depth- search is equivalent to the general heuristic search (including best-bound search as a special case). It is confirmed by computational experiment that the performance of depth-m search continuously changes from that, of depth-first search to that of heuristic search, whenm is changed from 1 to . The exact upper bound on the size of the required memory space is derived and shown to be bounded byO(n^m), wheren is the problem size. Some methods for controllingm during computation are also proposed and compared, to carry out the entire computation within a given memory space bound.     

Asymmetric Rendezvous Search on the Circle

The rendezvous search problem asks how two blind searchers in a known search region, having maximum speed one, can minimize the expected time needed to meet. Suppose that two players are placed an arc-distance x [ 0,1/2] apart on a circle of circumference 1, and faced in random directions. If x has a continuous density function h which is either decreasing and satisfies ht( 1/2) h(0)/2,or increasing, we determine an optimal rendezvous strategy. Furthermore if h is strictly monotone, this strategy (which depends in a simple manner on h) is uniquely optimal. This work extends that of J. V. Howard, who showed for the uniform density h(x) = 2 that search and wait is optimal , with expected search time 1/2. We also show that the uniform density is the only counterexample on the circle to S. Gal's conjecture (which he proved for the line) on the nonoptimality of search and wait.     

Minimization of norms and logarithmic norms by diagonal similarities

It is a commonly occurring problem to find good norms · or logarithmic norms (·) for a given matrix in the sense that they should be close to respectively the spectral radius (A) and the spectral abscissa (A). Examples may be the certification thatA is convergent, i.e. (A)A<1 or stable, i.e. (A)(A)<0. Often the ordinary norms do not suffice and one would like to try simple modifications of them such as using an ordinary norm for a diagonally transformed matrix. This paper treats this problem for some of the ordinary norms.

---

Minimisierung von Normen und Logarithmischen Normen durch Diagonale Transformationen

Zusammenfassung Ein oft vorkommendes praktisches Problem ist die Konstruktion von guten Normen · und logarithmischen Normen (·) für eine gegebene MatrixA. Mit gut wird dann verstanden, daß A den Spektralradius (A)=max |₁| und (A) die Spektralabszisse (A)=max Re _i gut approximieren. Beispiele findet man für konvergente Matrizen wo (A)A<1 gewünscht ist, und für stabile Matrizen wo (A)(A)<0 zu zeigen ist. Wir untersuchen hier, wie weit man mit Diagonaltransformationen und dengewöhnlichsten Normen kommen kann.

     

Regions-of-Interest and Spatial Layout for Content-Based Image Retrieval

To date most content-based image retrieval (CBIR) techniques rely on global attributes such as color or texture histograms which tend to ignore the spatial composition of the image. In this paper, we present an alternative image retrieval system based on the principle that it is the user who is most qualified to specify the query content and not the computer. With our system, the user can select multiple regions-of-interest and can specify the relevance of their spatial layout in the retrieval process. We also derive similarity bounds on histogram distances for pruning the database search. This experimental system was found to be superior to global indexing techniques as measured by statistical sampling of multiple users' satisfaction ratings.     

Undirecteds-t connectivity in polynomial time and sublinear space

Thes-t connectivity problem for undirected graphs is to decide whether two designated vertices,s andt, are in the same connected component. This paper presents the first known deterministic algorithms solving undirecteds-t connectivity using sublinear space and polynomial time. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. Forn vertex,m edge graphs, the simplest of our algorithms uses spaceO(s),n ^1/2log₂ nsnlog₂ n, and timeO(((m+n)n ² log² n)/s). We give a variant of this method that is faster at the higher end of the space spectrum. For example, with space (nlogn), its time bound isO((m+n)logn), close to the optimal time for the problem. Another generalization uses less space, but more time: spaceO(n ^1/logn), for 2log₂ n, and timen ^O(). For constant the time remains polynomial.     

SAT Local Search Algorithms: Worst-Case Study

Recent experiments demonstrated that local search algorithms (e.g. GSAT) are able to find satisfying assignments for many hard Boolean formulas. A wide experimental study of these algorithms demonstrated their good performance on some inportant classes of formulas as well as poor performance on some other ones. In contrast, theoretical knowledge of their worst-case behavior is very limited. However, many worst-case upper and lower bounds of the form 2 ⁿ (<1 is a constant) are known for other SAT algorithms, for example, resolution-like algorithms. In the present paper we prove both upper and lower bounds of this form for local search algorithms. The class of linear-size formulas we consider for the upper bound covers most of the DIMACS benchmarks; the satisfiability problem for this class of formulas is NP-complete.     

Interweaving Kohonen Maps of Different Dimensions to Handle Measure Zero Constraints on Topological Mappings

The usual Kohonen algorithm uses samples of points in a domain to develop a topological correspondence between a grid of neurons and a continuous domain. Topological means that near points are mapped to near points. However, for many applications there are additional constraints, which are given by sets of measure zero, which are not preserved by this method, because of insufficient sampling. In particular, boundary points do not typically map to boundary points because in general the likelihood of a sample point from a two-dimensional domain falling on the boundary is typically zero for continuous data, and extremely small for numerical data. A specific application, (assigning meshes for the finite element method), was recently solved by interweaving a two-dimensional Kohonen mapping on the entire grid with a one-dimensional Kohonen mapping on the boundary. While the precise method of interweaving was heuristic, the underlying rationale seems widely applicable. This general method is problem independent and suggests a direct generalization to higher dimensions as well.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

Integration of parametric and “ad hoc” second order polymorphism in a calculus with subtyping

In this paper we define an extension ofF [CUG92] to which we add functions that dispatch on different terms according to the type they receive as argument. In other words, we enrich the explicit parametric polymorphism ofF by an explicit ad hoc polymorphism (according the classification of [Str67]). We prove that the calculus we obtain, calledF ^& , enjoys the properties of Church-Rosser and Subject Reduction and that its proof system is coherent. We also define a significant subcalculus for which the subtyping is decidable. This extension has not only a logical interest but it is strongly motivated by the foundation of a broadly used programming style: object-oriented programming. The connections betweenF ^& and object-oriented languages are widely stressed, and the modelling byF ^& of some features of the object-oriented style is described, continuing the work of [CGL96].Part of this work has appeared under the title F ^& : integrating parametric and ad hoc second order polymorphism in the 4th International Workshop on Database Programming Languages. New York City, August 1993.The author was supported by grant n. 203.01.56 of the Consiglio Nazionale delle Ricerche-Comitato Nazionale delle Scienze Matematiche to work at LIENS.     

Continuous reductions among combinatorial optimization problems

Summary Many reductions among combinatorial problems are known in the context of NP-completeness. These reductions preserve the optimality of solutions. However, they may change the relative error of approximative solutions dramatically. In this paper, we apply a new type of reductions, called continuous reductions. When one problem is continuously reduced to another, any approximation algorithm for the latter problem can be transformed into an approximation algorithm for the former. Moreover, the performance ratio is preserved up to a constant factor. We relate the problem Minimum Number of Inverters in CMOS-Circuits, which arises in the context of logic synthesis, to several classical combinatorial problems such as Maximum Independent Set and Deletion of a Minimum Number of Vertices (Edges) in Order to Obtain a Bipartite (Partial) Subgraph.     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

Indecomposable local maps of tessellation automata

Indecomposable local maps of one-dimensional tessellation automata are studied. The main results of this paper are the following. (1) For any alphabet containing two or more symbols and for anyn 1, there exist indecomposable scope-n local maps over . (2) If is a finite field of prime order, then a linear scope-n local map over is indecomposable if and only if its associated polynomial is an irreducible polynomial of degreen – 1 over , except for a trivial case. (3) Result (2) is no longer true if is a finite field whose order is not prime.     

Directed explicit-state model checking in the validation of communication protocols

The success of model checking is largely based on its ability to efficiently locate errors in software designs. If an error is found, a model checker produces a trail that shows how the error state can be reached, which greatly facilitates debugging. However, while current model checkers find error states efficiently, the counterexamples are often unnecessarily lengthy, which hampers error explanation. This is due to the use of naive search algorithms in the state space exploration.In this paper we present approaches to the use of heuristic search algorithms in explicit-state model checking. We present the class of A^* directed search algorithms and propose heuristics together with bitstate compression techniques for the search of safety property violations. We achieve great reductions in the length of the error trails, and in some instances render problems analyzable by exploring a much smaller number of states than standard depth-first search. We then suggest an improvement of the nested depth-first search algorithm and show how it can be used together with A^* to improve the search for liveness property violations. Our approach to directed explicit-state model checking has been implemented in a tool set called HSF-SPIN. We provide experimental results from the protocol validation domain using HSF-SPIN.     

A “Microscopic” Study of Minimum Entropy Search in Learning Decomposable Markov Networks

Several scoring metrics are used in different search procedures for learning probabilistic networks. We study the properties of cross entropy in learning a decomposable Markov network. Though entropy and related scoring metrics were widely used, its microscopic properties and asymptotic behavior in a search have not been analyzed. We present such a microscopic study of a minimum entropy search algorithm, and show that it learns an I-map of the domain model when the data size is large.Search procedures that modify a network structure one link at a time have been commonly used for efficiency. Our study indicates that a class of domain models cannot be learned by such procedures. This suggests that prior knowledge about the problem domain together with a multi-link search strategy would provide an effective way to uncover many domain models.     

A multiprocessor working as a Fault-Tolerant cellular automaton

A memory-coupled multiprocessor—well suited to bit-wise operation—can be utilized to operate as a 1024 items cellular processing unit. Each processor is working on 32 bits and 32 such processors are combined to a multiprocessor. The information is stored in vertical direction, as it is defined and described in earlier papers [1] on vertical processing. The two-dimensional array (32 times 32 bits) is composed of the 32 bit-machine-words of the coupled processors on the one hand and of 32 processors in nearest-neighbour-topology on the other hand. The bit-wise cellular operation at one of the 1024 points is realized by the program of the processor—possibly assisted by appropriate microprogam sequences.Dedicated to Professor Willard L. Miranker on the occasion of his 60th birthday     

Browsers for distributed systems: Universal paradigm or siren's song?

Webbased browsers are quickly becoming ubiquitous in the workplace. Software development managers are quick to incorporate browsers into a broad range of software development projects, often inappropriately. The purpose of this paper is to examine the technical issues relevant to incorporating browsers as a component of a commercial offtheshelf (COTS)based solution. Issues examined include portability, performance, functionality, security, human factors, distribution, installation, upgrading, componentbased development, runtime configuration management, and licensing.     

Cockpit cognition: Education,the military and cognitive engineering

The goals of public education, as well as conceptions of human intelligence and learning, are undergoing a transformation through the application of military-sponsored information technologies and information processing models of human thought. Recent emphases in education on thinking skills, learning strategies, and computer-based technologies are the latest episodes in the postwar military agenda to engineer intelligent components, human and artificial, for the optimal performance of complex technological systems. Public education serves increasingly as a human factors laboratory and production site for this military enterprise, whose high performance technologies and command and control paradigms have also played central roles in the emergence of the information economy.Our final hope is to develop the brain as a natural resource ... Human intelligence will be the weapon of the future.Luis Alberto MachadoThis paper will also appear, under the title Mental Material inCyborg Worlds: The Military Information Society, eds. Les Levidow and Kevin Robins, London: Free Association Press, (in press).     

Boolean query optimization and the 0-1 hyperbolic sum problem

An intelligent front-end or logic assistant is an interactive program devised to assist the users of an information retrieval system in the formulation of their queries. In order to provide knowledge usable in such a program, we study a problem of query optimization with an average efficiency criterion. We formulate it as a new combinatorial optimization problem, which we call 0-1 hyperbolic sum, and provide an exact branch-and-bound algorithm and two heuristics (of simulated annealing and tabu search type) to solve it. Computational experience illustrating the effectiveness of the tabu search technique is reported.This research was done in part during a visit of the first author to the Pontifical Catholic University of Rio de Janeiro in July and August 1987, sponsored by CNPq. It was also supported in part by grants 0271 and 0066 of AFOSR to Rutgers University.     

Maintaining Longest Paths Incrementally

Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. This paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O( + || log||) time and O() time respectively, where || and are measures of the change in the input and output. The paper also shows how to generalize the algorithm to various classes of multiple insertions/deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice.     

The growth of configurations

The transition ruleF of a cellular automaton may sometimes be regarded as a rule of growth of a crystal from a seed. A study is made of the iterates,F,F ² .For certain one-dimensional growth rules, the limiting shapes of the crystals are computed, and an asymptotic formula for the size of the crystal as a function of time is obtained.