Multiplicative linear search for a brownian target motion

This paper investigates a search problem for a brownian target motion on one of n-intersected real lines in which any information of the target position is not available to the searchers all the time. We have n-searchers start searching for the target from the origin that is the intersection point of these lines. Each of the searchers moves continuously along his line in both directions of the starting point. The purpose of this paper is to formulate a search model and find the condition under which the expected value of the first meeting time between one of the searchers and the target is finite. Also, we show the existence of the optimal search plan which minimizes the expected value of the first meeting time and find it.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

A characterization of robert's inequality for boxicity

F.S. Roberts defined the boxicity of a graph G as the smallest positive integer n for which there exists a function F assigning to each vertex x?G a sequence F(x)(1),F(x)(2),…, F(x)(n) of closed intervals of R so that distinct vertices x and y are adjacent in G if and only if F(x)(i)∩F(y)(i)≠? fori = 1, 2, 3, …, n. Roberts then proved that if G is a graph having 2n + 1 vertices, thentheboxicityofGisatmostn. In this paper, we provide an explicit characterization of this inequality by determining for each n ? 1 the minimum collection $\text{C}$_n of graphs so that a graph G having 2n + 1 vertices has boxicity n if and only if it contains a graph from $\text{C}$_n as an induced subgraph. We also discuss combinatorial connections with analogous characterization problems for rectangle graphs, circular arc graphs, and partially ordered sets.     

Solving Linear Systems Whose Elements Are Nonlinear Functions of Intervals

The paper addresses the problem of solving linear algebraic systems the elements of which are, in the general case, nonlinear functions of a given set of independent parameters taking on their values within prescribed intervals. Three kinds of solutions are considered: (i) outer solution, (ii) interval hull solution, and (iii) inner solution. A simple direct method for computing a tight outer solution to such systems is suggested. It reduces, essentially, to inverting a real matrix and solving a system of real linear equations whose size n is the size of the original system. The interval hull solution (which is a NP-hard problem) can be easily determined if certain monotonicity conditions are fulfilled. The resulting method involves solving n+1 interval outer solution problems as well as 2n real linear systems of size n. A simple iterative method for computing an inner solution is also given. A numerical example illustrating the applicability of the methods suggested is solved.     

Short cycles of Poncelet’s conics

Main results of this paper are the following:1. A closed N-gon interscribed between two conics exists if and only if a specially constructed polygon with a smaller number of sides (n) is closed. To verify the closure of this n-gon, we need to find a periodic solution of a dynamical system of order n. The proof is based on the connection of Poncelet’s curves and matrices that admit unitary bordering [4,9,10,16]. Application of this criterion makes sense when n?N, in particular when n≈log₂N (see Table 4 where n=m₁). So for example we may say that a polygon with 2049 sides interscribed between two circles is closed if and only if some specially constructed 11-gon is closed.2. A closed N-gon interscribed between two confocal ellipses (the billiard case) exists if and only if an N-gon interscribed between two special nested circles is closed.     

Simulated annealing and tabu search approaches for the Corridor Allocation Problem

In the Corridor Allocation Problem, we are given n facilities to be arranged along a corridor. The arrangements on either side of the corridor should start from a common point on the left end of the corridor. In addition, no space is allowed between two adjacent facilities. The problem is motivated by applications such as the arrangement of rooms in office buildings, hospitals, shopping centers or schools. Tabu search and simulated annealing algorithms are presented to minimize the sum of weighted distances between every pair of facilities. The algorithms are evaluated on several instances of different sizes either randomly generated or available in the literature. Both algorithms reached the optimal (when available) or best-known solutions of the instances with n ? 30. For larger instances with size 42 ? n ? 70, the simulated annealing implementation obtained smaller objective values, while requiring a smaller number of function evaluations.     

A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case

Matrices A for which the upper bound per(A)?1+min{Π(c_i?1), Π(r_i?1)} holds with equality are characterized. Cases where the bound is achieved correspond to multigraphs with the property that there exists a unique path from any vertex to any disjoint cycle union. This occurs precisely when some multigraph associated with A has the mastercycle property: all cycles thread all branchpoints in the same circular order. Such multigraphs may also be characterized as a circular concatenation of certain acyclic multigraphs, each having a unique source and sink. This analysis yields two normal forms for the extremal matrices, one based on a nested block decomposition, and another based on an overlapping block decomposition. The extremal cases are invariant under contractions, yielding another characterization.     

The Existence and Application of Strongly Idempotent Self-orthogonal Row Latin Magic Arrays

Let N = {0, 1, · · ·, n ? 1}. A strongly idempotent self-orthogonal row Latin magic array of order n (SISORLMA(n) for short) based on N is an n × n array M satisfying the following properties: (1) each row of M is a permutation of N, and at least one column is not a permutation of N; (2) the sums of the n numbers in every row and every column are the same; (3) M is orthogonal to its transpose; (4) the main diagonal and the back diagonal of M are 0, 1, · · ·, n ? 1 from left to right. In this paper, it is proved that an SISORLMA(n) exists if and only if n ? {2, 3}. As an application, it is proved that a nonelementary rational diagonally ordered magic square exists if and only if n ? {2, 3}, and a rational diagonally ordered magic square exists if and only if n ≠ 2.     

Generating the alternating group by cyclic triples

It is shown that a collection of circular permutations of length three on an n-set generates the alternating group A_n if and only if the associated graph is connected. It follows that [$\text{1}\text{2}\text{n}$] circular permutations of length three may generateA_n.     

Scheduling Independent Tasks with Deadlines on Semi-identical Processors

Given m semi-identical processors which are parallel processors all working with the same speed but in different time intervals of availability and n independent tasks with deadlines, the problem of constructing a feasible pre-emptive schedule is examined. We present an O (nm log n) time algorithm to construct such a schedule whenever one exists. We show that the number of induced pre-emptions is proportional to the total number of processing intervals and deadlines.     

Generating sets for lattices of dimension two

The dimension of a partially ordered set P is the smallest integer n (if it exists) such that the partial order on P is the intersection of n linear orders. It is shown that if L is a lattice of dimension two containing a sublattice isomorphic to the modular lattice M_2n+1, then every generating set of L has at least n+2 elements. A consequence is that every finitely generated lattice of dimension two and with no infinite chains is finite.     

Commutativity of the adjacency matrices of graphs

We say that two graphs G₁ and G₂ with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers n such that the complete bipartite graph K_n,n is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most n−1 linearly independent commuting adjacency matrices of size n; and if this bound occurs, then there exists a Hadamard matrix of order n. Finally, we determine the centralizers of some families of graphs.     

On a characterization of tridiagonal matrices by M. Fiedler

In this note two new proofs are given of the following characterization theorem of M. Fiedler: Let C_n, n?2, be the class of all symmetric, real matrices A of order n with the property that rank (A + D) ? n - 1 for any diagonal real matrix D. Then for any A ε C_n there exists a permutation matrix P such that PAP^T is tridiagonal and irreducible.     

Existence of weakly pandiagonal orthogonal Latin squares

A weakly pandiagonal Latin square of order n over the number set {0, 1, . . . , n-1} is a Latin square having the property that the sum of the n numbers in each of 2n diagonals is the same. In this paper, we shall prove that a pair of orthogonal weakly pandiagonal Latin squares of order n exists if and only if n ≡ 0, 1, 3 (mod 4) and n≠3.     

Decomposition of complete multigraphs into crown graphs

Let λ K _v be the complete multigraph, G a finite simple graph. A G-design of λ K _v is denoted by GD(v,G,λ). The crown graph Q _n is obtained by joining single pendant edge to each vertex of an n-cycle. We give new constructions for Q _n -designs. Let v and λ be two positive integers. For n=4, 6, 8 and λ≥1, there exists a GD(v,Q _n ,λ) if and only if either (1) v>2n and λ v(v?1)≡0 (mod 4n), or (2) v=2n and λ≡0 (mod 4). Let n≥4 be even. Then (1) there exists a GD(2n,Q _n ,λ) if and only if λ≡0 (mod 4). (2) There exists a GD(2n+1,Q _n ,λ) when λ≡0 (mod 4).     

Monogamous latin squares

We show for all n∉{1,2,4} that there exists a latin square of order n that contains two entries γ₁ and γ₂ such that there are some transversals through γ₁ but they all include γ₂ as well. We use this result to show that if n>6 and n is not of the form 2p for a prime p?11 then there exists a latin square of order n that possesses an orthogonal mate but is not in any triple of MOLS. Such examples provide pairs of 2-maxMOLS.     

Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs

A straight-line drawing of a plane graph is called an open rectangle-of-influence drawing if there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of every edge. In an inner triangulated plane graph, every inner face is a triangle although the outer face is not necessarily a triangle. In this paper, we first obtain a sufficient condition for an inner triangulated plane graph G to have an open rectangle-of-influence drawing; the condition is expressed in terms of a labeling of angles of a subgraph of G. We then present an O(n ^1.5/log n)-time algorithm to examine whether G satisfies the condition and, if so, construct an open rectangle-of-influence drawing of G on an (n−1)×(n−1) integer grid, where n is the number of vertices in G.     

Irreducible Jacobian derivations in positive characteristic

We prove that an irreducible polynomial derivation in positive characteristic is a Jacobian derivation if and only if there exists an (n-1)-element p-basis of its ring of constants. In the case of two variables we characterize these derivations in terms of their divergence and some nontrivial constants.     

A new characterization of matrices with the consecutive ones property

We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment.     

On the Stability of Eaton’s Characterization by the Properties of Linear Forms

We consider a population and a sample X ₁,X ₂,…,X _n of n independent observations drawn from this population. We assume that two suitably chosen linear statistics of X ₁,X ₂,…,X _n are given. The assumption that these statistics are identically distributed or have the same distribution as the monomial X ₁ can be used to characterize various populations. This is an object of the so-called characterization theorems. But if the assumptions of a characterization theorem are fulfilled only approximately, then can we state that the conclusion of this characterization is also fulfilled approximately? Theorems concerning problems of this type are called stability theorems. By Eaton’s theorem, if, under additional conditions, two linear statistics $(X_{1}+\cdots +X_{k_{1}})/k_{1}^{1/\alpha}We consider a population and a sample X ₁,X ₂,…,X _n of n independent observations drawn from this population. We assume that two suitably chosen linear statistics of X ₁,X ₂,…,X _n are given. The assumption that these statistics are identically distributed or have the same distribution as the monomial X ₁ can be used to characterize various populations. This is an object of the so-called characterization theorems. But if the assumptions of a characterization theorem are fulfilled only approximately, then can we state that the conclusion of this characterization is also fulfilled approximately? Theorems concerning problems of this type are called stability theorems. By Eaton’s theorem, if, under additional conditions, two linear statistics and have the same distribution as the monomial X ₁, then this monomial has a symmetric stable distribution of order α. The stability estimation in this theorem is investigated in the λ ₀-metric.