Odd and even hamming spheres also have minimum boundary

Combinatorial problems with a geometric flavor arise if the set of all binary sequences of a fixed length n, is provided with the Hamming distance. The Hamming distance of any two binary sequences is the number of positions in which they differ. The (outer) boundary of a set A of binary sequences is the set of all sequences outside A that are at distance 1 from some sequence in A. Harper [6] proved that among all the sets of a prescribed volume, the ‘sphere’ has minimum boundary.We show that among all the sets in which no pair of sequences have distance 1, the set of all the sequences with an even (odd) number of 1's in a Hamming ‘sphere’ has the same minimizing property. Some related results are obtained. Sets with more general extremal properties of this kind yield good error-correcting codes for multi-terminal channels.     

On the complexity of growth of the number of distinct fuzzy switching functions

Several attempts have been made to enumerate fuzzy switching (FSF's) and to develop upper and lower bounds for the number of FSF's of n variables in an effort to better understand the properties and the complexity of FSF's. Previous upper bounds are 2⁴ⁿ [9] and 2^{2–3n—2n—1} [7].It has also been shown that the exact numbers of FSF's of n variables for n = 0, 1, 2, 3, and 4 are 2, 6, 8, 84, 43 918 and 160 297 985 276 respectively.This paper will give a brief overview of previous approaches to the problem, study some of the properties of fuzzy switching functions and give improved upper and lower bounds for a general n.     

A simple version of Karzanov's blocking flow algorithm

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n²). Karzanov devised the first O(n²)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n²)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.     

Another proof of dilworth's decomposition theorem

Dilworth's famous theorem [1] states that if the maximal sized antichains of a finite poset X have n elements, then X can be covered by n chains. The number n is called the width of X. Apart from proofs relating the theorem to other key theorems of combinatorics (see [1–4]), there have been a number of direct proofs (see [1, 2, 5, 6]). The shortest of these is the one by Perles [5], the outline of which is as follows.     

Convergent series solution of nonlinear equations

The author's decomposition method [1] provides a new, efficient computational procedure for solving large classes of nonlinear (and/or stochastic) equations. These include differential equations containing polynomial, exponential, and trigonometric terms, negative or irrational powers, and product nonlinearities [2]. Also included are partial differential equations [3], delay-differential equations [4], algebraic equations [5], and matrix equations [6] which describe physical systems. Essentially the method provides a systematic computational procedure for equations containing any nonlinear terms of physical significance. The procedure depends on calculation of the author's A_n, a finite set of polynomials [1,13] in terms of which the nonlinearities can be expressed. This paper shows important properties of the A_n which ensure an accurate and computable convergent solution by the author's decomposition method [1]. Since the nonlinearities and/or stochasticity which can be handled are quite general, the results are potentially extremely useful for applications and make a number of common approximations such as linearization, unnecessary.     

Two counterfeit coins

We consider the problem of ascertaining the minimum number of weighings which suffice to determine the counterfeit (heavier) coins in a set of n coins of the same appearance, given a balance scale and the information that there are exactly two heavier coins present. An optimal procedure is constructed for infinitely many n's, and for all other n's a lower bound and an upper bound for the maximum number of steps of an optimal precedure are determined which differ by just one unit. Some results of Cairns are improved, and his conjecture at the end of [3] is proved in a slightly modified form.     

Some results on Hu's conjecture concerning binary trees

Given n weights, w₁, w₂,…, w_n, such that 0?w₁?w₂???w₁, we examine a property of permutation π¹, where π¹=(w₁, w_n, w₂, w_n?1,…), concerning alphabetical binary trees.For each permutation π of these n weights, there is an optimal alphabetical binary tree corresponding to π, we denote it's cost by V(π). There is also an optimal almost uniform alphabetical binary tree, corresponding to π, we denote it's cost by V_u(π).This paper asserts that V_u(π¹)?V_u(π)?V(π) for all π. This is a preliminary result concerning the conjecture of T.C. Hu. Hu's conjecture is V(π¹)?V(π) for all π.     

An O(n log n) unidirectional distributed algorithm for extrema finding in a circle

In this paper we present algorithms, which given a circular arrangement of n uniquely numbered processes, determine the maximum number in a distributive manner. We begin with a simple unidirectional algorithm, in which the number of messages passed is bounded by 2 n log n + O(n). By making several improvements to the simple algorithm, we obtain a unidirectional algorithm in which the number of messages passed is bounded by 1.5nlogn + O(n). These algorithms disprove Hirschberg and Sinclair's conjecture that O(n²) is a lower bound on the number of messages passed in undirectional algorithms for this problem. At the end of the paper we indicate how our methods can be used to improve an algorithm due to Peterson, to obtain a unidirectional algorithm using at most 1.356nlogn + O(n) messages. This is the best bound so far on the number of messages passed in both the bidirectional and unidirectional cases.     

On the optimization of constrained functions: comparison of sequential gradient-restoration algorithm and gradient-projection algorithm

The problem of minimizing a function fnof(x) subject to the nonlinear constraint ?(x) = 0 is considered, where fnof is a scalar, x is an n-vector, and ? is a q-vector, with q < n. The sequential gradient-restoration algorithm (SGRA: Miele, [1, 2]) and the gradient-projection algorithm (GPA: Rosen, [3, 4]) are considered. These algorithms have one common characteristic: they are all composed of the alternate succession of gradient phases and restoration phases. However, they are different in several aspects, namely, (a) problem formulation, (b) structure of the gradient phase, and (c) structure of the restoration phase. First, a critical summary of SGRA and GPA is presented. Then, a comparison is undertaken by considering the speed of convergence and, above all, robustness (that is, the capacity of an algorithm to converge to a solution). The comparison is done through 16 numerical examples. In order to understand the separate effects of characteristics (a), (b), (c), six new experimental algorithms are generated by combining parts of Miele's algorithm with parts of Rosen's algorithm. Thus, the total number of algorithms investigated is eight. The numerical results show that Miele's method is on the average faster than Rosen's method. More importantly, regarding robustness, Miele's method compares favorably with Rosen's method. Through the examples, it is shown that Miele's advantage in robustness is more prominent as the curvature of the constraint increases. While this advantage is due to the combined effect of characteristics (a), (b), (c), it is characteristic (c) that plays the dominant role. Indeed, Miele's restoration provides a better search direction as well as better step-size control than Rosen's restoration.     

Calculation of the discrepancy of a finite set of points in the unit n-cube

An algorithm for calculating the discrepancy of finitely many points in the unit n-cube [0, 1]ⁿ is suggested. This algorithm is easy to program. For 2 ≤ n ≤ 4, the suggested algorithm is significantly faster than Bundschuh and Zhu’s algorithm. For larger n, whether this algorithm is faster depends on the number of points.     

The Pjateckiĭ-S̆apiro prime number theorem

It is proved that the sequence [n^c] contains the expected number of primes whenever 1 < c < 1.1404…, thus improving Kolesnik's range 1 < c < 1.1111…. An identity of Vaughan's type in five variables is needed.     

Finite dimensional convex structures II: the invariants

Various relations between the dimension and the classical invariants of a topological convex structure have been obtained, leading to an equivalence between Helly's and Carathéodory's theorem, and to the closedness of the hull of compact sets in finite-dimensional convexities. It is also shown that the Radon number of an n-dimensional binary convexity is in most cases equal to the Radon number of the n-cube, and a natural condition is presented under which the invariants are equal to dimension plus one.     

Three-graphs without two triples whose symmetric difference is contained in a third

Katona conjectured that if a three-graph has 3n vertices and n³+1 triples, then there are two triples whose symmetric difference is contained in a third triple. This conjecture can be considered as a natural generalization of Turán's theorem [4] for edge graphs. The aim of this note is to prove this conjecture.     

The measure problem for rectangular ranges in d-space

Klee recently posed the question: find an efficient algorithm for computing the measure of a set of n intervals on the line, and the analog for n hyperrectangles (ranges) in d-space. The one-dimensional case is easily solved in O(n log n) and Bentley has proved an O(n^d?1log n) algorithm for dimension d ≥ 2. We present an algorithm for Klee's measure problem that has a worst-case running time of only O(n^d?1) for d?3. While Bentley's algorithm is based on segment trees and requires only linear storage for any dimension, the new method is based on quad-trees and requires quadratic storage for d > 2.     

Matroids,generalized networks,and electric network synthesis

Matroid theory has been applied to solve problems in generalized assignment, operations research, control theory, network theory, flow theory, generalized flow theory or linear programming, coding theory, and telecommunication network design. The operations of matroid union, matroid partitioning, matroid intersection, and the theorem on the greedy algorithm, Rado's theorem, and Brualdi's symmetric version of Rado's theorem have been important for some of these applications. In this paper we consider the application of matroids to solve problems in network synthesis. Previously Bruno and Weinberg defined a generalized network, which is a network based on a matroid rather than a graph; for a generalized network the duality principle holds whereas it does not hold for a network based on a graph. We use the concept of the generalized network to formulate a solution to the following problem: What are the necessary and sufficient conditions for a singular matrix of real numbers, of order p and rank s, to be realizable as the open-circuit resistance matrix of a resistance p-port network. A simple algorithm is given for carriyng out the synthesis. We then present a number of unsolved problems, included among which is what could be called the four-color problem of network synthesis, namely, the resistance n-port problem.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

nth order Stieltjes differential boundary operators and Stieltjes differential boundary systems

This article discusses linear differential boundary systems, which include nth-order differential boundary relations as a special case, in $\text{L}$_n^p[0,1] × $\text{L}$_n^p[0,1], 1 ? p < ∞. The adjoint relation in $\text{L}$_n^q[0,1] × $\text{L}$_n^q[0,1], $\text{1}\text{p}\text{+}\text{1}\text{q}\text{= 1}$, is derived. Green's formula is also found. Self-adjoint relations are found in $\text{L}$_n²[0,1] × $\text{L}$_n²[0,1], and their connection with Coddington's extensions of symmetric operators on subspaces of $\text{L}$_n^p[0,1] × $\text{L}$_n²[0,1] is established.     

Integer programming formulation of combinatorial optimization problems

This paper considers in a somewhat general setting when a combinatorial optimization problem can be formulated as an (all-integer) integer programming (IP) problem. The main result is that any combinatorial optimization problem can be formulated as an IP problem if its feasible region S is finite but there are many rather sample problems that have no IP formulation if their S is infinite. The approach used for finite S usually gives a formulation with a relatively small number of additional variables for example, an integer polynomial of n 0?1 variables requires at most n + 1 additional variables by our approach, whereas 2ⁿ - (n + 1) additional variables at maximum are required by other existing methods. Finally, the decision problem of deciding whether an arbitrarily given combinatorial optimization problem has an IP formulation is considered and it is shown by an argument closely related to Hilbert's tenth problem (drophantine equations) that no such algorithm exists.     

Intrinsic ordering,combinatorial numbers and reliability engineering

A new algorithm for evaluating the top event probability of large fault trees (FTs) is presented. This algorithm does not require any previous qualitative analysis of the FT. Indeed, its efficiency is independent of the FT logic, and it only depends on the number n of basic system components and on their failure probabilities. Our method provides exact lower and upper bounds on the top event probability by using new properties of the intrinsic order relation between binary strings. The intrinsic order enables one to select binary n  -tuples with large occurrence probabilities without necessity to evaluate them. This drastically reduces the complexity of the problem from exponential (2ⁿ$2^n$ binary n-tuples) to linear (n Boolean variables). Our algorithm is mainly based on a recursive formula for rapidly computing the sum of the occurrence probabilities of all binary n-tuples with weight m whose 1s are placed among the k right-most positions. This formula, as well as the balance between accuracy and computational cost, is closely related to the famous Pascal’s triangle.     

Problem F2∥Cmax with forbidden jobs in the first or last position is easy

Saadani et al. [N.E.H. Saadani, P. Baptiste, M. Moalla, The simple F2∥C_max with forbidden tasks in first or last position: A problem more complex that it seems, European Journal of Operational Research 161 (2005) 21–31] studied the classical n-job flow shop scheduling problem F2∥C_max with an additional constraint that some jobs cannot be placed in the first or last position. There exists an optimal job sequence for this problem, in which at most one job in the first or last position is deferred from its position in Johnson’s [S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 (1954) 61–68] permutation. The problem was solved in O(n²) time by enumerating all candidate job sequences. We suggest a simple O(n) algorithm for this problem provided that Johnson’s permutation is given. Since Johnson’s permutation can be obtained in O(n log n) time, the problem in Saadani et al. (2005) can be solved in O(n log n) time as well.