One line and n points

We analyze a randomized pivoting process involving one line and n points in the plane. The process models the behavior of the RANDOM ‐EDGE simplex algorithm on simple polytopes with n facets in dimension n ? 2. We obtain a tight O(log² n) bound for the expected number of pivot steps. This is the first nontrivial bound for RANDOM ‐EDGE , which goes beyond bounds for specific polytopes. The process itself can be interpreted as a simple algorithm for certain 2‐variable linear programming problems, and we prove a tight Θ(n) bound for its expected runtime. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Colorful polytopes and graphs

The paper investigates connections between abstract polytopes and properly edge colored graphs. Given any finite n-edge-colored n-regular graph G, we associate to G a simple abstract polytope P _G of rank n, the colorful polytope of G, with 1-skeleton isomorphic to G. We investigate the interplay between the geometric, combinatorial, or algebraic properties of the polytope P _G and the combinatorial or algebraic structure of the underlying graph G, focussing in particular on aspects of symmetry. Several such families of colorful polytopes are studied including examples derived from a Cayley graph, in particular the graphicahedra, as well as the flagadjacency polytopes and related monodromy polytopes associated with a given abstract polytope. The duals of certain families of colorful polytopes have been important in the topological study of colored triangulations and crystallization of manifolds.     

A note on “Efficient feasibility testing for dial-a-ride problems”

Hunsaker and Savelsbergh [B. Hunsaker, M.W.P. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169-173.] developed a linear-time algorithm to verify the feasibility for dial-a-ride problems. However, this algorithm may incorrectly declare infeasibility due to ride time constraints in some cases. We propose a revised procedure to address this flaw, but in an O(n²) worst-case time.     

Polytopes of high rank for the alternating groups

There is a well-known correspondence between abstract regular polytopes and string C-groups. In this paper, for each d?3, a string C-group with d generators, isomorphic to an alternating group of degree n is constructed (for some n?9), or equivalently an abstract regular d-polytope, is produced with automorphism group Alt(n). A method that extends the CPR graph of a polytope to a different CPR graph of a larger (or possibly isomorphic) polytope is used to prove that various groups are themselves string C-groups.     

Approximating the fixed linear crossing number

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal “node line” in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k-cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878+0.122ρ approximation algorithm for FLCNP, where ρ is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family G_n,1/2, where each edge of the complete graph K_n occurs with probability . We show that a longstanding conjecture for the crossing number of K_n implies that with probability at least 1-4e^-λ2, the expected performance bound of the algorithm on a random graph from G_n,1/2 is 1.366+O(λ/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall.     

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     

Permutation polytopes and indecomposable elements in permutation groups

Each group G of n×n permutation matrices has a corresponding permutation polytope, P(G):=conv(G)⊂Rn×n. We relate the structure of P(G) to the transitivity of G. In particular, we show that if G has t nontrivial orbits, then min{2t,⌊n/2⌋} is a sharp upper bound on the diameter of the graph of P(G). We also show that P(G) achieves its maximal dimension of ²(n−1) precisely when G is 2-transitive. We then extend the results of Pak [I. Pak, Four questions on Birkhoff polytope, Ann. Comb. 4 (1) (2000) 83-90] on mixing times for a random walk on P(G). Our work depends on a new result for permutation groups involving writing permutations as products of indecomposable permutations.     

Mixing chiral polytopes

An abstract polytope of rank n is said to be chiral if its automorphism group has two orbits on the flags, such that adjacent flags belong to distinct orbits. Examples of chiral polytopes have been difficult to find. A ??mixing?? construction lets us combine polytopes to build new regular and chiral polytopes. By using the chirality group of a polytope, we are able to give simple criteria for when the mix of two polytopes is chiral.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

Observations on a class of nasty linear complementarity problems

Earlier papers by Murty [16] and Fathi [7] have exhibited classes of linear complementarity problems for which the computational effort (number of pivot steps) required to solve them by Lemke's algorithm [13] or Murty's algorithm [15] grows exponentially with the pronlem size (number of variables). In this paper we consider the sequences of complementary bases that arise as these problems are solved by the aforementioned algorithms. There is a natural correspondence between these bases and binary n-vectors through which the basis sequences can be identified with particular hamiltonian paths on the unit n-cube and with the binary Gray code representations of the integers from 0 to 2ⁿ-1.     

A sweep-plane algorithm for generating random tuples in simple polytopes

A sweep-plane algorithm of Lawrence for convex polytope computation is adapted to generate random tuples on simple polytopes. In our method an affine hyperplane is swept through the given polytope until a random fraction (sampled from a proper univariate distribution) of the volume of the polytope is covered. Then the intersection of the plane with the polytope is a simple polytope with smaller dimension.

In the second part we apply this method to construct a black-box algorithm for log-concave and -concave multivariate distributions by means of transformed density rejection.

     

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.     

A new algorithm for the intersection of a line with the independent set polytope of a matroid

We present a new algorithm for the problem of determining the intersection of a half-line with the independent set polytope of a matroid. We show it can also be used to compute the strength of a graph and the corresponding partition using successive contractions. The algorithm is based on the maximization of successive linear forms on the boundary of the polytope. We prove it is a polynomial algorithm in probability with average number of iterations in O(n⁵). Finally, numerical tests reveal that it should only require O(n²) iterations in practice.     

On randomized broadcasting in Star graphs

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. In this paper, we study the following robust, simple, and scalable randomized broadcasting protocol: at some time t an information is placed at one of the nodes of a graph G, and in the succeeding steps, each informed node chooses one of its neighbours in G uniformly at random, and sends the information to this neighbour.We show that this algorithm spreads an information to all nodes in a Star graph S_n of dimension n within O(logN) steps, with high probability, where N denotes the number of nodes in S_n. To obtain this result, we first establish lower bounds on the edge expansion of small subsets of nodes. Then we introduce a simple but powerful technique for estimating the runtime of randomized broadcasting by analyzing the protocol described above in the reverse order. Using this technique we can also simplify the analysis of this algorithm in Hypercubes [U. Feige, D. Peleg, P. Raghavan, E. Upfal, Randomized broadcast in networks, Random Structures and Algorithms 1 (4) (1990) 447-460].     

A polynomial time algorithm for a chance-constrained single machine scheduling problem

This paper gives an O(n√nlog³n) time algorithm for the chance-constrained sequencing problem on a single machine, where n is the number of jobs and the objective is to minimize the number of jobs which are early with probability not smaller than α (a given constant) against the common due time d.     

A polyhedral study of triplet formulation for single row facility layout problem

The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n−1)(n−2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.     

On pedigree polytopes and Hamiltonian cycles

In this paper we define a combinatorial object called a pedigree, and study the corresponding polytope, called the pedigree polytope. Pedigrees are in one-to-one correspondence with the Hamiltonian cycles on K_n. Interestingly, the pedigree polytope seems to differ from the standard tour polytope, Q_n with respect to the complexity of testing whether two given vertices of the polytope are nonadjacent. A polynomial time algorithm is given for nonadjacency testing in the pedigree polytope, whereas the corresponding problem is known to be NP-complete for Q_n. We also discuss some properties of the pedigree polytope and illustrate with examples.     

An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm

A random recursive tree on n vertices is either a single isolated vertex (for n=1) or is a vertex v_n connected to a vertex chosen uniformly at random from a random recursive tree on n−1 vertices. Such trees have been studied before [R. Smythe, H. Mahmoud, A survey of recursive trees, Theory of Probability and Mathematical Statistics 51 (1996) 1-29] as models of boolean circuits. More recently, Barabási and Albert [A. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509-512] have used modifications of such models to model for the web and other “power-law” networks.A minimum (cardinality) dominating set in a tree can be found in linear time using the algorithm of Cockayne et al. [E. Cockayne, S. Goodman, S. Hedetniemi, A linear algorithm for the domination number of a tree, Information Processing Letters 4 (1975) 41-44]. We prove that there exists a constant d?0.3745… such that the size of a minimum dominating set in a random recursive tree on n vertices is dn+o(n) with probability approaching one as n tends to infinity. The result is obtained by analysing the algorithm of Cockayne, Goodman and Hedetniemi.     

Embedding a polytope in a lattice

We present a special similarity ofR ⁴ⁿ which maps lattice points into lattice points. Applying this similarity, we prove that if a (4n−1)-polytope is similar to a lattice polytope (a polytope whose vertices are all lattice points) inR ⁴ⁿ , then it is similar to a lattice polytope inR ⁴ⁿ⁻¹, generalizing a result of Schoenberg [4]. We also prove that ann-polytope is similar to a lattice polytope in someR ^N if and only if it is similar to a lattice polytope inR ²ⁿ⁺¹, and if and only if sin²(<ABC) is rational for any three verticesA, B, C of the polytope.