An arc-search $${\mathcal {O}}(nL)$$ infeasible-interior-point algorithm for linear programming

Arc-search interior-point methods have been proposed to capture the curvature of the central path using an approximation based on ellipse. Yang et al. (J Appl Math Comput 51(1–2):209–225, 2016) proved that an arc-search algorithm has the computational order of \({\mathcal {O}}(n^{5/4}L)\). In this paper, we propose an arc-search infeasible-interior-point algorithms and discuss its convergence analysis. We improve the polynomial bound from \({\mathcal {O}}(n^{5/4}L)\) to \({\mathcal {O}}(nL)\), which is at least as good as the best existing bound for infeasible-interior-point algorithms for linear programming. Numerical results indicate that the proposed method solved LP instances faster than the existing \({\mathcal {O}}(n^{5/4}L)\) method.     

First-order algorithm with {\mathcal{O}({\rm ln}(1{/}\epsilon))} convergence for {\epsilon}-equilibrium in two-person zero-sum games

We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x \in Q_1}\max_{y \in Q_2} {x}^{\rm T}{Ay} = \max_{y \in Q_2} \min_{x \in Q_1} {x}^{\rm T}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an ${\epsilon}$ -equilibrium to this min-max problem in ${\mathcal {O}\left(\frac{\|A\|}{\delta(A)} \, {\rm ln}(1{/}\epsilon)\right)}$ first-order iterations, where δ(A) is a certain condition measure of the matrix A. This improves upon the previous first-order methods which required ${\mathcal {O}(1{/}\epsilon)}$ iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm’s dependence on ${\epsilon}$ . Unlike interior-point methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior first-order methods. Our scheme supplements Nesterov’s method with an outer loop that lowers the target ${\epsilon}$ between iterations (this target affects the amount of smoothing in the inner loop). Computational experiments both in matrix games and sequential games show that a significant speed improvement is obtained in practice as well, and the relative speed improvement increases with the desired accuracy (as suggested by the complexity bounds).     

An O（rL） Infeasible Interior-point Algorithm for Symmetric Cone LCP via CHKS Function

In this paper, we propose a theoretical framework of an infeasible interior-point algorithm for solving monotone linear cornplementarity problems over symmetric cones （SCLCP）. The new algorithm gets Newton-like directions from the Chen-Harker-Kanzow-Smale （CHKS） smoothing equation of the SCLCP. It possesses the following features： The starting point is easily chosen; one approximate Newton step is computed and accepted at each iteration; the iterative point with unit stepsize automatically remains in the neighborhood of central path; the iterative sequence is bounded and possesses （9（rL） polynomial-time complexity under the monotonicity and solvability of the SCLCP.     

An $$mathcal{O}(mlog n)$$ algorithm for the weighted stable set problem in claw-free graphs with $$alpha ({G}) le 3$$

Mathematical Programming - In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with $$alpha (G) le 3$$ in time $$mathcal{O}(|E|log...     

An efficient algorithm for mining high utility itemsets with negative item values in large databases

Utility itemsets typically consist of items with different values such as utilities, and the aim of utility mining is to identify the itemsets with highest utilities. In the past studies on utility mining, the values of utility itemsets were considered as positive. In some applications, however, an itemset may be associated with negative item values. Hence, discovery of high utility itemsets with negative item values is important for mining interesting patterns like association rules. In this paper, we propose a novel method, namely HUINIV (High Utility Itemsets with Negative Item Values)-Mine, for efficiently and effectively mining high utility itemsets from large databases with consideration of negative item values. To the best of our knowledge, this is the first work that considers the concept of negative item values in utility mining. The novel contribution of HUINIV-Mine is that it can effectively identify high utility itemsets by generating fewer high transaction-weighted utilization itemsets such that the execution time can be reduced substantially in mining the high utility itemsets. In this way, the process of discovering all high utility itemsets with consideration of negative item values can be accomplished effectively with less requirements on memory space and CPU I/O. This meets the critical requirements of temporal and spatial efficiency for mining high utility itemsets with negative item values. Through experimental evaluation, it is shown that HUINIV-Mine outperforms other methods substantially by generating much less candidate itemsets under different experimental conditions.     

An O(n2) algorithm for a controllable machine scheduling problem

A single-machine scheduling problem with controllable processingtimes is discussed in this paper. For some jobs, the processingtime can be crashed up to u units of time with the additionalcost c per unit of time crashed. The object is to find an optimalprocessing sequence as well as crash activities to minimizetotal costs of completion and crash. This problem is shown tobe polynomially solvable, and an O(n²) algorithm is given togetherwith the theoretical proof.     

Constant Angle Property and Canonical Principal Directions for Surfaces in {\mathbb{M}^{2}(c) \times {\mathbb{R}_{1}}}

In this paper, we study surfaces in Lorentzian product spaces ${{\mathbb{M}^{2}(c) \times \mathbb{R}_1}}$ . We classify constant angle spacelike and timelike surfaces in ${{\mathbb{S}^{2} \times \mathbb{R}_1}}$ and ${{\mathbb{H}^{2} \times \mathbb{R}_1}}$ . Moreover, complete classifications of spacelike surfaces in ${{\mathbb{S}^{2} \times \mathbb{R}_1}}$ and ${{\mathbb{H}^{2} \times \mathbb{R}_1}}$ and timelike surfaces in ${{\mathbb{M}^{2}(c) \times \mathbb{R}_1}}$ with a canonical principal direction are obtained. Finally, a new characterization of the catenoid of the 3rd kind is established, as the only minimal timelike surface with a canonical principal direction in Minkowski 3–space.     

Combinatorial invariants for nets of conics in $$\mathrm {PG}(2,q)$$ PG ( 2 , q )

Designs, Codes and Cryptography - The problem of classifying linear systems of conics in projective planes dates back at least to Jordan, who classified pencils (one-dimensional systems) of conics...     

An O(n2) shortest path algorithm for a non-rotating convex body

We investigate the problem of moving a convex body in the plane from one location to another while avoiding a given collection of polygonal obstacles. The method we propose is applicable when the convex body is not allowed to rotate. If n denotes the total size of all polygonal obstacles, the method yields an O(n²) algorithm for finding a shortest path from the initial to the final location. In solving this problem, we develop some new tools in computational geometry that may be of independent interest.     

An O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads

The large sparse linear systems arising from the finite element or finite difference discretization of elliptic PDEs can be solved directly via, e.g., nested dissection or multifrontal methods. Such techniques reorder the nodes in the grid to reduce the asymptotic complexity of Gaussian elimination from O(N ²) to O(N ^1.5) for typical problems in two dimensions. It has recently been demonstrated that the complexity can be further reduced to O(N) by exploiting structure in the dense matrices that arise in such computations (using, e.g., \(\mathcal {H}\) -matrix arithmetic). This paper demonstrates that such accelerated nested dissection techniques become particularly effective for boundary value problems without body loads when the solution is sought for several different sets of boundary data, and the solution is required only near the boundary (as happens, e.g., in the computational modeling of scattering problems, or in engineering design of linearly elastic solids). In this case, a modified version of the accelerated nested dissection scheme can execute any solve beyond the first in O(N _boundary) operations, where N _boundary denotes the number of points on the boundary. Typically, N _boundary ～ N ^0.5. Numerical examples demonstrate the effectiveness of the procedure for a broad range of elliptic PDEs that includes both the Laplace and Helmholtz equations.     

An O(n 2) active set algorithm for the solution of a parametric quadratic program

In this paper, an O(n ²) active set method is presented for minimizing the parametric quadratic function (1/2)x′Dx-a′x + λmax(c - γ x,0) subject to l ⩽ x ⩽ b, for all nonnegative values of the parameter γ. Here, D is a positive diagonal n x n matrix, a and γ are arbitrary N-vectors, c is an arbitrary scalar, l and b are arbitrary n-vectors, such thatl ⩽ b. An extension of this algorithm is presented for minimizing the parametric function (1/2)x′Dx-a ^′ x + λ |γ′x - c| subject to l ⩽ x ⩽ b. It is also shown that these problems arise naturally in a tax programming problem. This revised version was published online in August 2006 with corrections to the Cover Date.     

An O(n log n) algorithm for finding all repetitions in a string

Any nonempty string of the form xx is called a repetition. An O(n log n) algorithm is presented to find all repetitions in a string of lenght n. The algorithm is based on a linear algorithm to find all the new repetitions formed when two strings are concatenated. This linear algorithm is possible because new repetitions of equal length must occur in blocks with consecutive starting positions. The linear algorithm uses a variation of the Knuth-Morris-Pratt algorithm to find all partial occurrences of a pattern within a text string. It is also shown that no algorithm based on comparisons of symbols can improve O(n log n). Finally, some open problems and applications are suggested.     

An O (n2) heuristic algorithm for the directed Steiner minimal tree problem

This paper describes the design of an O(N²) heuristic algorithm for the Directed Steiner Minimal Tree (DSMT) problem in the plane. The algorithm employs the Delaunay triangulation, a minimum spanning arborescence algorithm, and a triangulation of the arborescence to develop solutions to the DSMT problem. Example applications are also included.     

Solving maximum clique in sparse graphs: an O(nm+n2^{d/4}) algorithm for d-degenerate graphs

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\) . The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\) . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.