Tight Hamilton cycles in random hypergraphs

We give an algorithmic proof for the existence of tight Hamilton cycles in a random r‐uniform hypergraph with edge probability for every . This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374–385), who used a second moment method to show that tight Hamilton cycles exist even for where arbitrary slowly, and for . The method we develop for proving our result applies to related problems as well. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 446–465, 2015     

Distance Preserving Recombination Operator for Earth Observation Satellites Operations Scheduling

The paper describes an adaptation of a memetic algorithm to the problem of scheduling operations of Earth observation satellites. The adaptation uses a systematic approach to the design of the recombination operator preserving important features common to both parents. The important features are identified experimentally on the basis of correlations between the value of the objective function and the similarity of good solutions. Our results indicate that this systematic approach reduces the effort needed to design a high quality recombination operator by avoiding not promising development directions.      

Circular mixed hypergraphs II:The upper chromatic number

A mixed hypergraph is a triple H=(X,C,D), where X is the vertex set and each of C, D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of H is a mapping c:X→[k] such that each C-edge has two vertices with a common color and each D-edge has two vertices with distinct colors. A mixed hypergraph H is called circular if there exists a host cycle on the vertex set X such that every edge (C- or D-) induces a connected subgraph of this cycle.We suggest a general procedure for coloring circular mixed hypergraphs and prove that if H is a reduced colorable circular mixed hypergraph with n vertices, upper chromatic number and sieve number s, then

     

Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-uniform k-partite hypergraphs.     

A lower bound on the independence number of arbitrary hypergraphs

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d(v) = (d₁(v), d₂(v), …) where d_m(v) is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ Σ_v∈V f(d(v)). This lower bound is sharp when H is a match, and it generalizes known bounds of Caro/Wei and Caro/Tuza for ordinary graphs and uniform hypergraphs. Furthermore, an algorithm for computing independent sets of size as guaranteed by the lower bound is given. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 213–221, 1999     

A note on near‐optimal coloring of shift hypergraphs

As shown in the original work on the Lovász Local Lemma due to Erd?s & Lovász (Infinite and Finite Sets, 1975), a basic application of the Local Lemma answers an infinitary coloring question of Strauss, showing that given any integer set S, the integers may be k‐colored so that S and all its translates meet every color. The quantitative bounds here were improved by Alon, Kriz & Nesetril (Studia Scientiarum Mathematicarum Hungarica, 1995). We obtain an asymptotically optimal bound in this note, using the technique of iteratively applying the Lovász Local Lemma in order to prune dependencies. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 53–56, 2016     

A note on the maximum size of Berge-C4-free hypergraphs

In this paper, we consider maximum possible value for the sum of cardinalities of hyperedges of a hypergraph without a Berge 4-cycle. We significantly improve the previous upper bound provided by Gerbner and Palmer. Furthermore, we provide a construction that slightly improves the previous lower bound.     

An approach to evolving novel organizational forms

A key problem in organization theory is to suggest new organizational forms. In this paper, I suggest the use of genetic algorithms to search for novel organizational forms by reproducing some of the mechanics of organizational evolution. Issues in using genetic algorithms include identification of the unit of selection, development of a representation and determination of a method for calculating organizational fitness. As an example of the approach, I test a proposition of Thompson's about how interdependent positions should be assigned to groups. Representing an organization as a collection of routines might be more general and still amenable to evolution with a genetic algorithm. I conclude by discussing possible objections to the application of this technique.Syracuse University School of Information Studies     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

A new complex approach towards approximate inverse and generalized Radon transform

In this paper, we first consider the framework of Sobolev spaces and derive analytically a reconstruction algorithm by means of the residue theorem of complex analysis, the approximate inverse, Gaussian mollifier and integral equations. And we successfully extend Natterer’s results to the generalized Radon transform with non-uniform attenuation. Finally, we investigate the smoothing properties of the generalized Radon transform.     

A label semantics approach to linguistic hedges

We introduce a model for the linguistic hedges ‘very’ and ‘quite’ within the label semantics framework, and combined with the prototype and conceptual spaces theories of concepts. The proposed model emerges naturally from the representational framework we use and as such, has a clear semantic grounding. We give generalisations of these hedge models and show that they can be composed with themselves and with other functions, going on to examine their behaviour in the limit of composition.     

On flows associated to Sobolev vector fields in Wiener spaces: An approach à la DiPerna-Lions

In this paper we extend the DiPerna-Lions theory of flows associated to Sobolev vector fields to the case of Cameron-Martin-valued vector fields in Wiener spaces E having a Sobolev regularity. The proof is based on the analysis of the continuity equation in E, and on uniform (Gaussian) commutator estimates in finite-dimensional spaces.     

A new parallel chasing algorithm for transforming arrowhead matrices to tridiagonal form

Rutishauser, Gragg and Harrod and finally H.Y. Zha used the same class of chasing algorithms for transforming arrowhead matrices to tridiagonal form. Using a graphical theoretical approach, we propose a new chasing algorithm. Although this algorithm has the same sequential computational complexity and backward error properties as the old algorithms, it is better suited for a pipelined approach. The parallel algorithm for this new chasing method is described, with performance results on the Paragon and nCUBE. Comparison results between the old and the new algorithms are also presented.

     

A Taxonomy of Evolutionary Algorithms in Combinatorial Optimization

This paper shows how evolutionary algorithms can be described in a concise, yet comprehensive and accurate way. A classification scheme is introduced and presented in a tabular form called TEA (Table of Evolutionary Algorithms). It distinguishes between different classes of evolutionary algorithms (e.g., genetic algorithms, ant systems) by enumerating the fundamental ingredients of each of these algorithms. At the end, possible uses of the TEA are illustrated on classical evolutionary algorithms.     

A new approach to superfractals

V-variable fractals and superfractals have recently been introduced by Barnsley [Barnsley Michael, Hutchinson John, Stenflo Örjan. A fractal valued random iteration algorithm and fractal hierarchy. Fractals 2005;13(2):111–46 [MR2151094 (2006b:28014)]] to the world of mathematics and computer graphics. In this paper, we introduce superior iterates to study the role of contractive and non-contractive operators in relation to superfractals. A modified algorithm along with details of computer implementation is also provided to compute V-variable fractals. A brief discussion about the various aspects of the computed figures indicates usefulness of the study.