A Class of Inverse Dominant Problems under Weighted l ∞ Norm and an Improved Complexity Bound for Radzik’s Algorithm

In this paper, we first discuss a class of inverse dominant problems under weighted l_∞ norm, which is how to change the original weights of elements with bounds in a finite ground set so that a given set becomes a weakly dominant set with respect to a given collection of subsets under the new weights and the largest change of the weights is minimum. This model includes a large class of improvement problems in combinatorial optimization. We propose a Newton-type algorithm for the model. This algorithm can solve the model in strongly polynomial time if the subproblem involved is solvable in strongly polynomial time. In the second part of the paper, we improve the complexity bound for Radzik’s Newton-type method which is designed to solve linear fractional combinatorial optimization problems. As Radzik’s method is closely related to our algorithm, this bound also estimates the complexity of our algorithm. Supported by the Hong Kong Universities Grant Council (CERG CITYU 9040883 and 9041091). Xiaoguang Yang - The author is also grateful for the support by the National Key Research and Development Program of China (Grant No. 2002CB312004) and the National Natural Science Foundation of China (Grant No. 70425004).     

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization

Bisubmodular functions are a natural “directed”, or “signed”, extension of submodular functions with several applications. Recently Fujishige and Iwata showed how to extend the Iwata, Fleischer, and Fujishige (IFF) algorithm for submodular function minimization (SFM) to bisubmodular function minimization (BSFM). However, they were able to extend only the weakly polynomial version of IFF to BSFM. Here we investigate the difficulty that prevented them from also extending the strongly polynomial version of IFF to BSFM, and we show a way around the difficulty. This new method gives a somewhat simpler strongly polynomial SFM algorithm, as well as the first combinatorial strongly polynomial algorithm for BSFM. This further leads to extending Iwata’s fully combinatorial version of IFF to BSFM. The research of S. T. McCormick was supported by an NSERC Operating Grant. The research of S. Fujishige was supported by a Grant-in-Aid of the Ministry of Education, Culture, Science and Technology of Japan.     

Leading coefficients of Kazhdan–Lusztig polynomials for Deodhar elements

We show that the leading coefficient of the Kazhdan–Lusztig polynomial P _x,w (q) known as μ(x,w) is always either 0 or 1 when w is a Deodhar element of a finite Weyl group. The Deodhar elements have previously been characterized using pattern avoidance in Billey and Warrington (J. Algebraic Combin. 13(2):111–136, [2001]) and Billey and Jones (Ann. Comb. [2008], to appear). In type A, these elements are precisely the 321-hexagon avoiding permutations. Using Deodhar’s algorithm (Deodhar in Geom. Dedicata 63(1):95–119, [1990]), we provide some combinatorial criteria to determine when μ(x,w)=1 for such permutations w. The author received support from NSF grants DMS-9983797 and DMS-0636297.     

A faster capacity scaling algorithm for minimum cost submodular flow

We describe an O(n ⁴ hmin{logU,n ²logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow. Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001     

Gray Codes,Loopless Algorithm and Partitions

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process.      

Pivoting in Extended Rings for Computing Approximate Gr?bner Bases

It is well known that in the computation of Gr?bner bases arbitrarily small perturbations in the coefficients of polynomials may lead to a completely different staircase, even if the solutions of the polynomial system change continuously. This phenomenon is called artificial discontinuity in Kondratyev’s Ph.D. thesis. We show how such phenomenon may be detected and even “repaired” by using a new variable to rename the leading term each time we detect a “problem”. We call such strategy the TSV (Term Substitutions with Variables) strategy. For a zero-dimensional polynomial ideal, any monomial basis (containing 1) of the quotient ring can be found with the TSV strategy. Hence we can use TSV strategy to relax term order while keeping the framework of Gr?bner basis method so that we can use existing efficient algorithms (for instance the F ₅ algorithm) to compute an approximate Gr?bner basis. Our main algorithms, named TSVn and TSVh, can be used to repair artificial e{\epsilon}-discontinuities. Experiments show that these algorithms are effective for some nontrivial problems.     

An acceleration method for Ten Berge et al.’s algorithm for orthogonal INDSCAL

INDSCAL (INdividual Differences SCALing) is a useful technique for investigating both common and unique aspects of K similarity data matrices. The model postulates a common stimulus configuration in a low-dimensional Euclidean space, while representing differences among the K data matrices by differential weighting of dimensions by different data sources. Since Carroll and Chang proposed their algorithm for INDSCAL, several issues have been raised: non-symmetric solutions, negative saliency weights, and the degeneracy problem. Orthogonal INDSCAL (O-INDSCAL) which imposes orthogonality constraints on the matrix of stimulus configuration has been proposed to overcome some of these difficulties. Two algorithms have been proposed for O-INDSCAL, one by Ten Berge, Knol, and Kiers, and the other by Trendafilov. In this paper, an acceleration technique called minimal polynomial extrapolation is incorporated in Ten Berge et al.’s algorithm. Simulation studies are conducted to compare the performance of the three algorithms (Ten Berge et al.’s original algorithm, the accelerated algorithm, and Trendafilov’s). Possible extensions of the accelerated algorithm to similar situations are also suggested.     

Linearity of grid minors in treewidth with applications through bidimensionality

We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has an Ω(w) × Ω(w) grid graph as a minor. Thus grid minors suffice to certify that H-minorfree graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms. A preliminary version of this paper appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) [16].     

On dual minimum cost flow algorithms

We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general problems (like submodular flow) and is likely to be more efficient in practice.  Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running time of our algorithm by a factor of n.     

Palindromic Prefixes and Diophantine Approximation

This article is devoted to simultaneous approximation to ξ and ξ² by rational numbers with the same denominator, where ξ is an irrational non-quadratic real number. We focus on an exponent β₀(ξ) that measures the regularity of the sequence of all exceptionally precise such approximants. We prove that β₀(ξ) takes the same set of values as a combinatorial quantity that measures the abundance of palindromic prefixes in an infinite word w. This allows us to give a precise exposition of Roy’s palindromic prefix method. The main tools we use are Davenport-Schmidt’s sequence of minimal points and Roy’s bracket operation.     

Second Order Cones for Maximal Monotone Operators via Representative Functions

It is shown that various first and second order derivatives of the Fitzpatrick and Penot representative functions for a maximal monotone operator T, in a reflexive Banach space, can be used to represent differential information associated with the tangent and normal cones to the Graph T. In particular we obtain formula for the proto-derivative, as well as its polar, the normal cone to the graph of T. First order derivatives are shown to be useful in recognising points of single-valuedness of T. We show that a strong form of proto-differentiability to the graph of T, is often associated with single valuedness of T. The second author’s research was funded by NSERC and the Canada Research Chair programme, and the first author’s by ARC grant number DP0664423. This study was commenced between August and December 2005 while the first author was visiting Dalhousie University.     

Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda’s Theorem

Toda (in SIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy, PH, is contained in the class P ^#P , namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class #P. This result, which illustrates the power of counting, is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum–Shub–Smale real machines in Bull. Am. Math. Soc. (NS) 21(1): 1–46, 1989) has been missing so far. In this paper we formulate and prove a real analogue of Toda’s theorem. Unlike Toda’s proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques, we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry: the problem of deciding sentences in the first-order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result may be of independent interest to researchers in algorithmic semi-algebraic geometry.     

Free lattice algorithms

In the late 1930s Phillip Whitman gave an algorithm for deciding for lattice terms v and u if vu in the free lattice on the variables in v and u. He also showed that each element of the free lattice has a shortest term representing it and this term is unique up to commutivity and associativity. He gave an algorithm for finding this term. Almost all the work on free lattices uses these algorithms. Building on the work of Ralph McKenzie, J. B. Nation and the author have developed very efficient algorithms for deciding if a lattice term v has a lower cover (i.e., if there is a w with w covered by v, which is denoted by w) and for finding them if it does. This paper studies the efficiency of both Whitman's algorithm and the algorithms of Freese and Nation. It is shown that although it is often quite fast, the straightforward implementation of Whitman's algorithm for testing vu is exponential in time in the worst case. A modification of Whitman's algorithm is given which is polynomial and has constant minimum time. The algorithms of Freese and Nation are then shown to be polynomial.     

Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs

We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.     

Mind the gap: a heuristic study of subway tours

What is the minimum tour visiting all lines in a subway network? In this paper we study the problem of constructing the shortest tour visiting all lines of a city railway system. This combinatorial optimization problem has links with the classic graph circuit problems and operations research. A broad set of fast algorithms is proposed and evaluated on simulated networks and example cities of the world. We analyze the trade-off between algorithm runtime and solution quality. Time evolution of the trade-off is also captured. Then, the algorithms are tested on a range of instances with diverse features. On the basis of the algorithm performance, measured with various quality indicators, we draw conclusions on the nature of the above combinatorial problem and the tacit assumptions made while designing the algorithms.     

Extended formulations in combinatorial optimization

This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski–Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes.     

<Emphasis Type="Italic">P</Emphasis>-adic continued fractions

We study Schneider’s p-adic continued fraction algorithms. For p=2, we give a combinatorial characterization of rational numbers that have terminating expansions. For arbitrary p, we give data showing that rationals with terminating expansions are relatively rare. Finally, we prove an analogue of Khinchin’s theorem.     

A decomposition algorithm for linear relaxation of the weightedr-covering problem

In this paper the linear relaxation of the weightedr-covering problem (r-LCP) is considered. The dual problem (c-LMP) is the linear relaxation of the well-knownc-matching problem and hence can be solved in polynomial time. However, we describe a simple, but nonpolynomial algorithm in which ther-LCP is decomposed into a sequence of 1-LCP’s and its optimal solution is obtained by adding the optimal solutions of these 1-LCP’s. An 1-LCP can be solved in polynomial time by solving its dual as a max-flow problem on a bipartite graph. An accelerated algorithm based on this decomposition scheme to solve ar-LCP is also developed and its average case behaviour is studied.     

Fractional covers for forests and matchings

We give polynomial algorithms for the fractional covering problems for forests andb-matchings: min{1·y: yA≥w,y≥0} whereA is a matrix whose rows are the incidence vectors of forests/b-matchings respectively. It is shown that each problem can be solved by a series of max-flow/min-cut calculations, and hence the use of the ellipsoid algorithm to guarantee a polynomial algorithm can be avoided. Visiting professor at the European Institute for Advanced Studies in Management in Brussels and at CORE. Supported in part by the CIM. On leave from New York University, New York, NY 10006.     

A Characterization of the Tutte Polynomial via Combinatorial Embeddings

We give a new characterization of the Tutte polynomial of graphs. Our characterization is formally close (but inequivalent) to the original definition given by Tutte as the generating function of spanning trees counted according to activities. Tutte’s notion of activity requires a choice of a linear order on the edge set (though the generating function of the activities is, in fact, independent of this order). We define a new notion of activity, the embedding-activity, which requires a choice of a combinatorial embedding of the graph, that is, a cyclic order of the edges around each vertex. We prove that the Tutte polynomial equals the generating function of spanning trees counted according to embedding-activities. This generating function is, in fact, independent of the embedding. Received March 15, 2006