Algorithms for maximum independent sets

An algorithm is presented which finds (the size of) a maximum independent set of an n vertex graph in time O(2^0.276n) improving on a previous bound of $\text{O(2}{}^{\mathrm{<mtext>n</mtext><mtext>3</mtext>}}\text{)}$. The improvement comes principally from three sources: first, a modified recursive algorithm based on a more detailed study of the possible subgraphs around a chosen vertex; second, an improvement, not in the algorithm but in the time bound proved, by an argument about connected regular graphs; third, a time-space trade-off which can speed up recursive algorithms from a fairly wide class.     

Parametric shortest path algorithms with an application to cyclic staffing

Let G=(V, E) be a digraph with n vertices including a special vertex s. Let E′ ? E be a designated subset of edges. For each e?E there is an associated real number $\text{?}{}_1\text{(e)}$. Furthermore, let $\text{?}{}_2\text{(e)=1}$ if e?E′ and $\text{?}{}_2\text{(e)=0}$ if e?E ? E′. The length of edge e is $\text{?}{}_1\text{(e)? λ?}{}_2\text{(e)}$, where λ is a parameter that takes on real values. Thus the length varies additively in λ for each edge of E′.We shall present two algorithms for computing the shortest path from s to each vertex υ?V parametrically in the parameter λ, with respective running times O(n³) and O(n|E|log n). For dense digraphs the running time of the former algorithm is comparable to the fastest (non-parametric) shortest path algorithm known.This work generalizes the results of Karp [2] concerning the minimum cycle mean of a digraph, which reduces to the case that E′=E. Furthermore, the second parametric algorithm may be used in conjunction with a transformation given by Bartholdi, Orlin, and Ratliff [1] to give an O(n² log n) algorithm for the cyclic staffing problem.     

Heuristic matching for graphs satisfying the triangle inequality

Two matching heuristics are presented. The hyper-greedy method runs in time O(n²log n) and produces a matching whose cost is at most 2log₃(1.5n) times optimal. Graphs are given causing this method to achieve nearly this ratio. The factor of two method runs in time O(n²log K), where K is the maximum ratio of edge lengths in the graph, and never requires more than O(n³) time. The factor of two method produces a matching whose cost is at most max(4log₂K, 4log₂n) times optimal, plus lower-order terms. Graphs are given causing this method to achieve a ratio asymptotically equal to $\text{(}\text{log}{}_2\text{n)}\text{2}$.     

Fast approximation algorithm for job sequencing with deadlines

The problem under consideration is to schedule jobs on a machine in order to minimize the sum of the penalties of delayed jobs. A “range-and-bound” method is proposed for finding a tight bound P? such that P?≤P1≤2P?, P1 being the minimal sum desired. The considered scheduling problem, for n jobs and accuracy ε > 0, is solved by a fully polynomial ε-approximation algorithm in $\text{O(n}{}^2\text{log n +}\text{n}{}^2\text{ε}\text{)}$ time and $\text{O(}\text{n}{}^2\text{ε}\text{)}$ space.     

A note on the functional law of iterated logarithm for maxima of Gaussian sequences

Let {X_n, n ≥ 1} be a real-valued stationary Gaussian sequence with mean zero and variance one. Let M_n = max{X_t, i ≤ n} and H_n(t) = (M_[nt] ? b_n)a_n^?1 be the maximum resp. the properly normalised maximum process, where $\text{c}{}_{\mathrm{n}}\text{= (2}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, $\text{a}{}_{\mathrm{n}}\text{=}\text{(}\text{log log}\text{n)}\text{c}{}_{\mathrm{n}}$ and $\text{b}{}_{\mathrm{n}}\text{= c}{}_{\mathrm{n}}\text{?}\text{1}\text{2}\text{(}\text{log}\text{(4π}\text{log}\text{n))}\text{c}{}_{\mathrm{n}}$. We characterize the almost sure limit functions of (H_n)_n≥3 in the set of non-negative, non-decreasing, right-continuous, real-valued functions on (0, ∞), if r(n) (log n)^3?Δ = O(1) for all Δ > 0 or if r(n) (log n)^2?Δ = O(1) for all Δ > 0 and r(n) convex and fulfills another regularity condition, where r(n) is the correlation function of the Gaussian sequence.     

Average running time of the fast Fourier transform

We compare several algorithms for computing the discrete Fourier transform of n numbers. The number of “operations” of the original Cooley-Tukey algorithm is approximately 2nA(n), where A(n) is the sum of the prime divisors of n. We show that the average number of operations satisfies $\text{1}\text{x}\text{)∑}{}_{\mathrm{n\le x}}\text{2n A(n) ～ (}\text{π}{}^2\text{9}\text{)(}\text{x}{}^2\text{log}\text{x}\text{)}$. The average is not a good indication of the number of operations. For example, it is shown that for about half of the integers n less than x, the number of “operations” is less than n^1.61. A similar analysis is given for Good's algorithm and for two algorithms that compute the discrete Fourier transform in O(n log n) operations: the chirp-z transform and the mixed-radix algorithm that computes the transform of a series of prime length p in O(p log p) operations.     

Retarded equations on the sphere induced by linear equations

Using a Poincaré compactification, the linear homogeneous system of delay equations {x = Ax(t ? 1) (A is an n × n real matrix) induces a delay system π(A) on the sphere Sⁿ. The points at infinity belong to an invariant submanifold S^{n ? 1} of Sⁿ. For an open and dense set of 2 × 2 matrices A with distinct eigenvalues, the system π(A) has only hyperbolic critical points (including the critical points at infinity). For an open and dense set of 2 × 2matrices $\text{A}$ with complex eigenvalues, the nonwandering set at infinity is the union of an odd number of hyperbolic periodic orbits; if $\text{(}\text{det}\text{A}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{<}\text{3π}\text{2}$, the restriction of $\text{π(}\text{A}\text{)}$ to S¹ is Morse-Smale. For n = 1 there exist periodic orbits of period 4 provided that $\text{?A >}\text{π}\text{2}$ and Hopf bifurcation of a center occurs for ?A near $\text{(}\text{π}\text{2}\text{) + 2kπ, k ? Z}$.     

Hecke operators and an identity for the dedekind sums

If h, k ∈ Z, k > 0, the Dedekind sum is given by

$\text{s(h,k) =}\text{∑}\text{μ=1}\text{k}\text{μ}\text{k}\text{hμ}\text{k}$

, with

$\text{((x)) = x ? [x] ?}\text{1}\text{2}\text{, x?Z}$

,

$\text{=0 , x∈Z}$

. The Hecke operators T_n for the full modular group SL(2, Z) are applied to log η(τ) to derive the identities (n ∈ Z⁺)

$\text{∑ ∑ s(ah+bk,dk) = σ(n)s(h,k)}$

,

$\text{ad=n b(}\text{mod}\text{d)}$

$\text{d>0}$

where (h, k) = 1, k > 0 and σ(n) is the sum of the positive divisors of n. Petersson had earlier proved (1) under the additional assumption k ≡ 0, h ≡ 1 (mod n). Dedekind himself proved (1) when n is prime.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

Fast solution of toeplitz systems of equations and computation of Padé approximants

We present two new algorithms, ADT and MDT, for solving order-n Toeplitz systems of linear equations Tz = b in time O(n log²n) and space O(n). The fastest algorithms previously known, such as Trench's algorithm, require time $\text{Ω(n}{}^2\text{)}$ and require that all principal submatrices of T be nonsingular. Our algorithm ADT requires only that T be nonsingular. Both our algorithms for Toeplitz systems are derived from algorithms for computing entries in the Padé table for a given power series. We prove that entries in the Padé table can be computed by the Extended Euclidean Algorithm. We describe an algorithm EMGCD (Extended Middle Greatest Common Divisor) which is faster than the algorithm HGCD of Aho, Hopcroft and Ullman, although both require time O(n log²n), and we generalize EMGCD to produce PRSDC (Polynomial Remainder Sequence Divide and Conquer) which produces any iterate in the PRS, not just the middle term, in time O(n log²n). Applying PRSDC to the polynomials U₀(x) = x²ⁿ⁺¹ and U₁(x) = a₀ + a₁x + … + a_2nx²ⁿ gives algorithm AD (Anti-Diagonal), which computes any (m, p) entry along the antidiagonal m + p = 2n of the Padé table for U₁ in time O(n log²n). Our other algorithm, MD (Main-Diagonal), computes any diagonal entry (n, n) in the Padé table for a normal power series, also in time O(n log²n). MD is related to Schönhage's fast continued fraction algorithm. A Toeplitz matrix T is naturally associated with U₁, and the (n, n) Padé approximation to U₁ gives the first column of T^?1. We show how a formula due to Trench can be used to compute the solution z of Tz = b in time O(n log n) from the first row and column of T^?1. Thus, the Padé table algorithms AD and MD give O(n log²n) Toeplitz algorithms ADT and MDT. Trench's formula breaks down in certain degenerate cases, but in such cases a companion formula, the discrete analog of the Christoffel-Darboux formula, is valid and may be used to compute z in time O(n log²n) via the fast computation (by algorithm AD) of at most four Padé approximants. We also apply our results to obtain new complexity bounds for the solution of banded Toeplitz systems and for BCH decoding via Berlekamp's algorithm.     

A lower estimate for the achromatic number of irreducible graphs

The achromatic number of a graph is the largest number of independent sets its vertex set can be split into in such a way that the union of any two of these sets is not independent. A graph is irreducible if no two vertices have the same neighborhood. The achromatic number of an irreducible graph with n vertices is shown to be $\text{≥(}\text{1}\text{2}\text{?0(1))log}\text{n?}\text{log log}\text{n,}$ while an example of Erdös shows that it need not be log n/log 2+2 for any n. The proof uses an indiscernibility argument.     

On finding the K best cuts in a network

We show that the O(K · n⁴) algorithm of Hamacher (1982) for finding the K best cut-sets fails because it may produce cuts rather than cut-sets. With the convention that two cuts $\text{(X,}\text{X}\text{)}$ and $\text{(Y,}\text{Y}\text{)}$ are different whenever X ≠ Y the K best cut problem can be solved in O(K · n⁴).     

A note on the similarity depth

In this note we demonstrate the existence of E0L forms F and G which are n-similar, i.e. $\text{L}$ⁿ(F) = $\text{L}$ⁿ(G) but $\text{L}$ⁿ⁺¹(F)≠$\text{L}$ⁿ⁺¹(G) for n ∈ {2, 3}. This partially solves an open problem from [3].     

Probabilistic analysis of solving the assignment problem for the traveling salesman problem

This paper deals with probabilistic analysis of optimal solutions of the asymmetric traveling salesman problem. The exact distribution for the number of required next-best solutions of the assignment problem with random data in order to find an optimal tour is given. For every n-city asymmetric problem, there exists an algorithm such that (i) with probability 1 ? s, s?(0,1) the algorithm produces an optimal tour, (ii) it runs in time $\text{O}\text{(}\text{n}{}^4\text{3}\text{)}$, and (iii) it requires less than w((w + n ? 1)$\text{log}\text{(w + n ? 1) + w + 1) +}\text{1}\text{6}\text{w(n}{}^3\text{+ 3n}{}^2\text{+ 2n ? 6)}$ computational steps, where w = log(s)/log(1 ? E_n); E_n ?(0,1) is given by a simple mathematical formula. Additionally, the polynomial of (iii) gives the exact (deterministic) execution time to find w =1 ,2…. next-best solutions of the assignment problem.