Inexpensive d‐dimensional matchings

Suppose that independent U(0, 1) weights are assigned to the ${d\choose 2}n^{2}$ edges of the complete d‐partite graph with n vertices in each of the d maximal independent sets. Then the expected weight of the minimum‐weight perfect d‐dimensional matching is at least $\frac{3}{16}n^{1-(2/d)}$. We describe a randomized algorithm that finds a perfect d‐dimensional matching whose expected weight is at most 5d³n^1?(2/d)+d¹⁵ for all d≥3 and n≥1. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 50–58, 2002     

An adjustable approach to fuzzy soft set based decision making

Molodtsov’s soft set theory was originally proposed as a general mathematical tool for dealing with uncertainty. Recently, decision making based on (fuzzy) soft sets has found paramount importance. This paper aims to give deeper insights into decision making based on fuzzy soft sets. We discuss the validity of the Roy-Maji method and show its true limitations. We point out that the choice value designed for the crisp case is no longer fit to solve decision making problems involving fuzzy soft sets. By means of level soft sets, we present an adjustable approach to fuzzy soft set based decision making and give some illustrative examples. Moreover, the weighted fuzzy soft set is introduced and its application to decision making is also investigated.     

A functional equation having monomials as solutions

For each n=1,2,3, we obtain the general solution and the stability of the functional equation

f(2x+y)+f(2x-y)=2^n-2[f(x+y)+f(x-y)+6f(x)].     

Double complex and gamma-monomials in global function fields

We investigate Γ-monomials of positive characteristic Γ-functions in the global function fields by using Anderson's double complex method. The results are the generalizations of those in the rational function field case.     

The design of an efficient load balancing algorithm employing block design

In order to maintain load balancing in a distributed system, we should obtain workload information from all the nodes on network. This processing requiresO(v ²) communication overhead, wherev is the number of nodes. In this paper, we present a new synchronous dynamic distributed load balancing algorithm on a (v, k+1, 1)-configured network applying a symmetric balanced incomplete block design, wherev=k ²+k+1. Our algorithm needs only $O(v\sqrt v )$ communication overhead and each node receives workload information from all the nodes without redundancy. Therefore, load balancing is maintained since every link has the same amount of traffic for transferring workload information.     

Possible isolation number of a matrix over nonnegative integers

Let ?₊ be the semiring of all nonnegative integers and A an m × n matrix over ?₊. The rank of A is the smallest k such that A can be factored as an m × k matrix times a k×n matrix. The isolation number of A is the maximum number of nonzero entries in A such that no two are in any row or any column, and no two are in a 2 × 2 submatrix of all nonzero entries. We have that the isolation number of A is a lower bound of the rank of A. For A with isolation number k, we investigate the possible values of the rank of A and the Boolean rank of the support of A. So we obtain that the isolation number and the Boolean rank of the support of a given matrix are the same if and only if the isolation number is 1 or 2 only. We also determine a special type of m×n matrices whose isolation number is m. That is, those matrices are permutationally equivalent to a matrix A whose support contains a submatrix of a sum of the identity matrix and a tournament matrix.     

Aperture-Angle and Hausdorff-Approximation of Convex Figures

The aperture angle α(x,Q) of a point x ∉ Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q⊂C is the minimum aperture angle of any x∈C∖Q with respect to Q. We show that for any compact convex set C in the plane and any k>2, there is an inscribed convex k-gon Q⊂C with aperture angle approximation error . This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance σ, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k>2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most  . This research was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-311-D00763). NICTA is funded through the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.     

Fuzzy convex sets in median algebras

The fuzzification of convex sets in median algebras is considered, and some of their properties are investigated. A characterization of finite valued fuzzy convex set is given.