On the insertion time of random walk cuckoo hashing

Cuckoo Hashing is a hashing scheme invented by pervious study of Pagh and Rodler. It uses d ≥ 2 distinct hash functions to insert n items into the hash table of size m = (1 + ε)n. In their original paper they treated d = 2 and m = (2 + ε)n. It has been an open question for some time as to the expected time for Random Walk Insertion to add items when d > 2. We show that if the number of hash functions d ≥ d_ε = O(1) then the expected insertion time is O(1) per item.     

The number of limit cycles of cubic Hamiltonian system with perturbation

In this paper, by using qualitative analysis, we investigate the number of limit cycles of perturbed cubic Hamiltonian system with perturbation in the form of (2n+2m) or (2n+2m+1)th degree polynomials . We show that the perturbed systems has at most (n+m) limit cycles, and has at most n limit cycles if m=1. If m=1, n=1 and m=1, n=2, the general conditions for the number of existing limit cycles and the stability of the limit cycles will be established, respectively. Such conditions depend on the coefficients of the perturbed terms. In order to illustrate our results, two numerical examples on the location and stability of the limit cycles are given.     

Total domination of graphs and small transversals of hypergraphs

The main result of this paper is that every 4-uniform hypergraph on n vertices and m edges has a transversal with no more than (5n + 4m)/21 vertices. In the particular case n = m, the transversal has at most 3n/7 vertices, and this bound is sharp in the complement of the Fano plane. Chvátal and McDiarmid [5] proved that every 3-uniform hypergraph with n vertices and edges has a transversal of size n/2. Two direct corollaries of these results are that every graph with minimal degree at least 3 has total domination number at most n/2 and every graph with minimal degree at least 4 has total domination number at most 3n/7. These two bounds are sharp.     

Dynamics and control of underactuated mechanical systems: analysis and simple experimental verification

Underactuated mechanical systems are systems with fewer control inputs than the degrees of freedom, m < n, the relevant technical examples being e.g. cranes, aircrafts and flexible manipulators. The determination of an input control strategy that forces an underactuated system to complete a set of m specified motion tasks (servo-constraints) is a demanding problem. The solution is conditioned to differential flatness of the problem, denoted that all 2n state variables and m control inputs can algebraically be expressed, at least theoretically, in terms of the desired m outputs and their time derivatives up to a certain order. A more practical formulation, motivated hereafter, is to pose the problem as a set of differential-algebraic equations, and then obtain the solution numerically. The theoretical considerations are illustrated by a simple two-degree-of-freedom underactuated system composed of two rotating discs connected by a flexible rod (torsional spring), in which the pre-specified motion of the first disc is actuated by the torque applied to the second disc, n = 2 and m = 1. The determined control strategy is then verified experimentally on a laboratory stand representing the two-disc system. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

A systolic generation of combinations

A parallel algorithm for generating all combinations ofm (m fixed) items out of anyn given items in lexicographic order is presented. The computational model is a linear systolic array consisting ofm identical processing elements. This algorithm requires {ie23-1} time-steps for the {ie23-2} combinations, that is, one output at each time-step. Since all processing elements perform the same program, it is suitable for VLSI implementation. Based on mathematical induction, such an algorithm is proved to be correct.     

Semi-Balanced Colorings of Graphs: Generalized 2-Colorings Based on a Relaxed Discrepancy Condition

We generalize the concept of a 2-coloring of a graph to what we call a semi-balanced coloring by relaxing a certain discrepancy condition on the shortest-paths hypergraph of the graph. Let G be an undirected, unweighted, connected graph with n vertices and m edges. We prove that the number of different semi-balanced colorings of G is: (1) at most n+1 if G is bipartite; (2) at most m if G is non-bipartite and triangle-free; and (3) at most m+1 if G is non-bipartite. Based on the above combinatorial investigation, we design an algorithm to enumerate all semi-balanced colorings of G in O(nm²) time.Acknowledgments The authors thank Tetsuo Asano, Naoki Katoh, Kunihiko Sadakane, and Hisao Tamaki for helpful discussions and comments.Supported in part by Sweden-Japan FoundationFinal version received: November 17, 2003     

Little-Preemptive Scheduling on Unrelated Processors

We consider the preemptive scheduling of n independent jobs on m unrelated machines to minimize the makespan. Preemptive schedules with at most 2m–3 preemptions are built, which are optimal when the maximal job processing time is no more than the optimal schedule makespan. We further restrict the maximal job processing time and obtain optimal schedules with at most m–1 preemptions. This is better than the earlier known best bound of 4m ²–5m+2 on the total number of preemptions. Without the restriction on the maximal job processing time, our (2m–3)-preemptive schedules have a makespan which is no more than either of the following two magnitudes: (a) the maximum between the longest job processing time and the optimal preemptive makespan, and (b) the optimal nonpreemptive makespan. Our (m–1)-preemptive schedules might be at most twice worse than an optimal one.     

Tournament games and positive tournaments

Given a tournament T, the tournament game on T is as follows: Two players independently pick a node of T. If both pick the same node, the game is tied. Otherwise, the player whose node is at the tail of the arc connecting the two nodes wins. We show that the optimal mixed strategy for this game is unique and uses an odd number of nodes. A tournament is positive if the optimal strategy for its tournament game uses all of its nodes. The uniqueness of the optimal strategy then gives a new tournament decomposition: any tournament can be uniquely partitioned into positive subtournaments P₁, P₂, ?,P_k, so P_i “beats” P_j for all 1 ≤ i > j ≤ k. We count the number of n node positive tournaments and list them for n ≤ 7. © 1995 John Wiley & Sons, Inc.     

Van der waerden and ramsey type games

Let us consider the following 2-player game, calledvan der Waerden game. The players alternately pick previously unpicked integers of the interval {1, 2, ...,N}. The first player wins if he has selected all members of ann-term arithmetic progression. LetW*(n) be the least integerN so that the first player has a winning strategy. By theRamsey game on k-tuples we shall mean a 2-player game where the players alternately pick previously unpicked elements of the completek-uniform hypergraph ofN verticesK _N ^k , and the first player wins if he has selected allk-tuples of ann-set. LetR _k*(n) be the least integerN so that the first player has a winning strategy. We prove (W* (n))¹/n → 2,R ₂*(n)<(2+ε) ⁿ andR _k ^* n<2 ^nk / ^k! fork ≧3.     

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.     

On m-step Fibonacci sequence in discrete Lotka-Volterra system

The integrable Lotka-Volterra (LV) system stands for a prey-predator model in mathematical biology. The discrete LV (dLV) system is derived from a time-variable discretization of the LV system. The solution to the dLV system is known to be represented by using the Hankel determinants. In this paper, we show that, if the entries of the Hankel determinants become m-step Fibonacci sequences at the initial discrete-time, then those are also so at any discrete time. In other words, the m-step Fibonacci sequences always arrange in the entries of the Hankel determinants under the time-variable evolution of the dLV system with suitable initial setting. Here the 2-step and the 3-step Fibonacci sequences are the famous Fibonacci and Tribonacci sequences, respectively. We also prove that one of the dLV variables converges to the ratio of two successive and sufficiently large m-step Fibonacci numbers, for example, the golden ratio in the case where m=2, as the discrete-time goes to infinity. Some examples are numerically given.     

Symmetric latin square and complete graph analogues of the evans conjecture

With the proof of the Evans conjecture, it was established that any partial latin square of side n with a most n ? 1 nonempty cells can be completed to a latin square of side n. In this article we prove an analogous result for symmetric latin squares: a partial symmetric latin square of side n with an admissible diagonal and at most n ? 1 nonempty cells can be completed to a symmetric latin square of side n. We also characterize those partial symmetric latin squares of side n with exactly n or n + 1 nonempty cells which cannot be completed. From these results we deduce theorems about completing edge-colorings of complete graphs K_2m and K_{2m ? 1} with 2m ? 1 colors, with m + 1 or fewer edges getting prescribed colors. © 1994 John Wiley & Sons, Inc.     

On a dual version of the one-dimensional bin packing problem

The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of , , and the optimal number, at running time costs of O(n), O(nlogn), and O(nlog²n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items.     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

A class of polynomially solvable linear complementarity problems

Although the general linear complementarity problem (LCP) is NP-complete, there are special classes that can be solved in polynomial time. One example is the type where the defining matrix is nondegenerate and for which the n-step property holds. In this paper we consider an extension of the property to the degenerate case by introducing the concept of an extended n-step vector and matrix. It is shown that the LCP defined by such a matrix is polynomially solvable as well.     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

A note on a spanning 3-tree

A tree T is called a k-tree, if the maximum degree of T is at most k. In this paper, we prove that if G is an n-connected graph with independence number at most n + m + 1 (n≥1,n≥m≥0), then G has a spanning 3-tree T with at most m vertices of degree 3.     

Nash equilibria in random games

We consider Nash equilibria in 2‐player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m × n payoff matrices, it runs in time O(m²nloglog n + n²mloglog m) with high probability. Our result follows from showing that a 2‐player random game has a Nash equilibrium with supports of size two with high probability, at least 1 − O(1/log n). Our main tool is a polytope formulation of equilibria. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Asymptotic enumeration of sparse 2‐connected graphs

We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on n vertices and m edges, provided that m ‐ n →∞ and m = O(nlog n) as n →∞. This is the entire range of m not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2‐edge‐connectedness is treated similarly. We also obtain formulae for the number of 2‐connected graphs with given degree sequence for most (“typical”) sequences. Our main result solves a problem of Wright from 1983. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013