Search

In this paper we present a new iteration-complexity bound for the Mizuno--Todd--Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program min {cTχ: Aχ = b, &chi ≥ 0 } with decision variable ..., we show that the MTY P-C algorithm, started from a well-centered interior-feasible solution with duality gap nμ0 finds an interior-feasible solution with duality gap less than nn in O (T(μ0/η)+n3.5 log (Χ*A)) iterations, where T(t ) =min {n² log (log t), log t} for all t>0 and Χ*A is a scaling invariant condition number associated with the matrix A. More specifically,Χ*A is the infimum of all the conditions numbers XAD, where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O (n3.5 LA + min {n² log L, L}) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where LA and L are the input sizes of the matrix A and the data (A,b,c ), respectively. This contrasts well with the classical iteration-complexity bound for the MTY P-C algorithm, which depends linearly on L instead of log L. [ABSTRACT FROM AUTHOR]

This paper presents a parameter-free integer-programming-based algorithm for the global resolution of a linear program with linear complementarity constraints {LPCCs). The cornerstone of the algorithm is a mini max integer program formulation that characterizes and provides certificates for the three outcomes—infeasibility, unboundedness, or solvability—of an LPCC. An extreme point/ray generation scheme in the spirit of Benders decomposition is developed, from which valid inequalities in the form of satisfiability constraints are obtained. The feasibility problem of these inequalities and the carefully guided linear-programming relaxations of the LPCC are the workhorses of the algorithm, which also employs a specialized procedure for the sparsification of the satifiability cuts. We establish the finite termination of the algorithm and report computational results using the algorithm for solving randomly generated LPCCs of reasonable sizes. The results establish that the algorithm can handle infeasible, unbounded, and solvable LPCCs effectively. [ABSTRACT FROM AUTHOR]

Abstract. We consider the problem of embedding weighted hyperedges of a hypergraph as paths in a cycle on the same number of vertices, such that the maximum congestion of any physical link of the cycle is minimized. The problem, called weighted hypergraph embedding in a cycle (WHEC), is known to be NP-complete even when each hyperedge is unweighted or each weighted hyperedge contains exactly two vertices. In this paper, we propose an improved rounding algorithm for the WHEC problem to provide a solution with an approximation bound of 1.5{opt +Wmax), where opt represents the optimal value of the problem and Wmax denotes the largest weight of hyperedges. For any fixed ∈ > 0, we also present a polynomial time algorithm to provide an embedding whose congestion is at most {1.5 + ∈) times the optimum. This improves previous results for the general WHEC problem. [ABSTRACT FROM AUTHOR]