Narrow Results

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differs by at most 1, and its size is the number of edges that go across the two parts. In this paper, motivated by a well-known result of Edwards about Max-Cut, we study maximum bisections of graphs. Let ${𝒢}=\{P_{\ell }⊠P_k,P_{\ell }⊠C_k,C_{\ell }⊠C_k\}$. For each $G\in {𝒢}$, we show that $G$ admits a bisection of size larger than Edwards’ bound. We also study the maximum bisection of graphs that seem closely related to the strong product of two paths.

Binary search trees with costs α and β on the left and right edges (lopsided binary search trees) are important in the construction of optimum prefix codes. In this paper we derive lower bounds for the external pathlengths of lopsided binary trees. It is found that the lower bound is tight if the cost difference (the difference in maximum cost and the minimum cost) is small but quite sharp when the cost difference is large. We suggest alternative ways to construct the lopsided binary tree when the cost difference is high to improve the lower bound.

Given a hexagonal cellular network with specific demand Vector and frequency separation constraints, we introduce the concept of a critical block of the network, that leads us to an efficient channel assignment scheme for the whole network. A novel idea of partitioning the critical block into several smaller sub-networks with homogeneous demands has been introduced which provides an elegant way of assigning frequencies to the critical block. This idea of partitioning is then extended for assigning frequencies to the rest of the network. The proposed algorithm provides an optimal assignment for all well-known benchmark instances including the most difficult two. It is shown to be superior to the existing frequency assignment algorithms, reported so far, in terms of both bandwidth requirement and computation time.

An asymptotic lower bound for the maxrun function ρ(n) = max {number of runs in string x | all strings x of length n} is presented. More precisely, it is shown that for any ε > 0, (α−ε)n is an asymptotic lower bound, where . A recent construction of an increasing sequence of binary strings “rich in runs” is modified and extended to prove the result.

This paper presents a new lower bound for the model-checking algorithm based on solving parity games due to Stevens and Stirling. We outline a family of games of linear size on which the algorithm requires exponential time.

This paper further explores the phase transitions of the EXPSPACE-complete problems, focusing on the conformant plan modification. By analyzing features of the conformant plan modification, quantitative results are obtained. If the number of actions is't greater than θ_ub, almost all the conformant planning instances can't be solved with the conformant plan modification. If the number of actions is't lower than θ_lb, almost all the conformant planning instances can be solved with the conformant plan modification. The results of the experiments show that there indeed exists an experimental threshold γ_c of density (ratio of number of actions to number of propositions), which separates the region where almost all conformant planning instances can't be solved with the conformant plan modification from the region where almost all conformant planning instances can be solved with the conformant plan modification.

In this paper, we study bounds for optimal constant dimension codes further. By revising the construction for constant dimension codes in [4], we improve some bounds on q-ary constant dimension codes in some cases. By combinatorial method, we show that there exists no optimal constant dimension code A_q[n, 2δ, k] meeting both Wang-Xing-Safavi-Naini-Bound and the maximal distance separate bound simultaneously.

In distributed storage systems, codes with lower repair locality for each coordinate are much more desirable since they can reduce the disk I/O complexity for repairing a failed node. The ith coordinate of a linear code 𝒞 is said to have $(r_i,{\delta }_i)$ locality if there exist δ_i non-overlapping local repair sets of size no more than r_i, where a local repair set of one coordinate is defined as the set of some other coordinates by which one can recover the value at this coordinate. In this paper, we consider linear codes with information $(r_{\min },{\delta }_{\min };r_{\max },{\delta }_{\max })$ locality, where there exists an information set I such that for each $i\in I$, the ith coordinate has $(r_i,{\delta }_i)$ locality and $\min \{r_i:i\in I\}=r_{\min ,}\max \{r_i:i\in I\}=r_{\max ,}\min \{{\delta }_i:i\in I\}={\delta }_{\min }$ and $max\{{\delta }_i:i\in I\}={\delta }_{\max }$. We derive a lower bound on the codeword length n for any linear [n, k, d] code with information $(r_{\min },{\delta }_{\min };r_{\max },{\delta }_{\max })$ locality. Particularly, we indicate that some existing bounds can be deduced from our result by restrictions on parameters.

Using a directed acyclic graph (dag) model of algorithms, we solve a problem related to precedence-constrained multiprocessor schedules for array computations: Given a sequence of dags and linear schedules parametrized by n, compute a lower bound on the number of processors required by the schedule as a function of n. In our formulation, the number of tasks that are scheduled for execution during any fixed time step is the number of non-negative integer solutions d_n to a set of parametric linear Diophantine equations. We present an algorithm based on generating functions for constructing a formula for these numbers d_n. The algorithm has been implemented as a Mathematica program. Example runs and the symbolic formulas for processor lower bounds automatically produced by the algorithm for Matrix-Vector Product, Triangular Matrix Product, and Gaussian Elimination problems are presented. Our approach actually solves the following more general problem: Given an arbitrary r× s integral matrix A and r-dimensional integral vectors b and c, let d_n(n=0,1,…) be the number of solutions in non-negative integers to the system Az=nb+c. Calculate the (rational) generating function ∑_{n≥ 0}d_ntⁿ and construct a formula for d_n.

We give a lower bound for the first Dirichlet eigenvalue for a compact manifold with positive Ricci curvature in terms of the lower bound of the Ricci curvature and the interior radius. The result sharpens earlier estimates.

We present a very simple new distributed algorithm for the classical Dining Philosophers problem.

Our algorithm is the first algorithm with the following important properties:

(1) It is fully distributed; i.e., there is no central memory or central process to which every other process may have access.

(2) It is symmetric; i.e., all processes behave identically, and do not use any process identifiers.

(3) It has a response time ≤ 3ℓ, independent of the size of the ring, where ℓ is an upper bound on the time a resource may be used by a process. Moreover, we establish the optimality of our algorithm with respect to this last measure by proving that no distributed algorithm can guarantee a response time less than 3ℓ.

The purpose of this study is to present a simple lower bound to facilitate the development of branch-and-bound algorithms for the minimization of total completion time in a two-machine flowshop. The studied problem is known to be strongly NP-hard. In the literature, several lower bounds have been proposed. The bounding technique addressed in this paper is based upon a concept about rearrangement of the parameters of the input instance. The technique is intrinsically simple for computer implementations. We conduct computational experiments for problems with 10–65 jobs. Numerical results from our computational study indicate that the new scheme is very effective in reducing the execution time needed for composing optimal solutions.

In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. We propose a lower bounding procedure based on the relaxation of the jobs' completion times. Optimal branch-and-bound algorithms are then presented. These algorithms incorporate the proposed lower bound, as well as an insertion-based dominance test.

The branch-and-bound procedures are tested on a wide set of randomly generated problems. The computational results show that the branch-and-bound algorithms are capable of optimally solving, within reasonable computation times, instances with up to 20 jobs.

In this paper, we consider a map labeling problem where the points to be labeled are restricted on a line. It is known that the 1d-4P and the 1d-4S unit-square label placement problem and the Slope-4P unit-square label placement problem can both be solved in linear time and the Slope-4S unit-square label placement problem can be solved in quadratic time in Ref. [8]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label or elastic label placement problem and present a linear time algorithm for it provided that the input points are given sorted. We further show that if the points are not sorted, the label placement problems have a lower bound of Ω(n log n), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered.

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem.

1. Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247.

2. Each embedding of a closed convex curve has dilation ≥ 1.00157.

3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation .

How many Reidemeister moves do we need for unknotting a given diagram of the trivial knot? The absolute value of the writhe gives a lower bound of the number of Reidemeister I moves. That of a complexity of knot diagram "cowrithe" works for Reidemeister II, III moves.

In Appendix A, we give an example of an infinite sequence of diagrams D_n of the trivial knot with an O(n) number of crossings such that the author expects the number of Reidemeister moves needed for unknotting it to be O(n²). However, writhe and cowrithe do not prove this.

A 3-dimensional consecutive k-out-of-n : F system consists of n³ components disposed on a cubic grid of size n; it fails if and only if all the components of at least one cube of size k (1 < k < n) fail (k³ components). Although introduced as early as in 1992 by Salvia and Lasher⁷ as a better model for problems in medical imaging, few results are known about it.¹ In this paper, we propose, in the the independent and not-necessarily-identical case, a new lower bound which has the advantage of being calculated directly from the reliability of a one dimensional consecutive-k-out-of-n:F system. To do this, we derive an intermediate system² which behaves like a one dimensional consecutive k-out-of-n and is less reliable than the initial 3-dimensional system, hence its suitability as the lower bound. The proposed approach converts a three-dimensional system into a one-dimensional system directly. It can be extended to the three-dimensional versions of the k-within-connected-(r,s,t)-out-of-(m,n,p):F system and the m-consecutive-k-out-of-n : F system.

In this paper, we investigate eigenvalues of fractional Laplacian (–Δ)^α/2|_D, where α ∈ (0, 2], on a bounded domain in an n-dimensional Euclidean space and obtain a sharper lower bound for the sum of its eigenvalues, which improves some results due to Yildirim Yolcu and Yolcu in [Estimates for the sums of eigenvalues of the fractional Laplacian on a bounded domain, Commun. Contemp. Math. 15(3) (2013) 1250048]. In particular, for the case of Laplacian, we obtain a sharper eigenvalue inequality, which gives an improvement of the result due to Melas in [A lower bound for sums of eigenvalues of the Laplacian, Proc. Amer. Math. Soc. 131 (2003) 631–636].

Let ψ = Γ′/Γ, where Γ is the Gamma function, and let x ≥ 0 and 0 < a ≤ b. Then

In this paper, we show that the radius of analyticity $\sigma (t)$ of solutions to the one-dimensional nonlinear Schrödinger (NLS) equation