Abstract In 1992, Kalai and Kleitman proved that the diameter of a d -dimensional polyhedron with n facets is at most n 2 + log 2 d . In 2014, Todd improved the Kalai–Kleitman bound to ( n − d ) log 2 d . We improve the Todd bound to ( n − d ) − 1 + log 2 d for n ≥ d ≥ 7 , ( n − d ) − 2 + log 2 d for n ≥ d ≥ 37 , and ( n − d ) − 3 + log 2 d + O 1 ∕ d for n ≥ d ≥ 1 .
Another well-studied parameter would be @math which is defined as the largest absolute value of a subdeterminant of the constraint matrix @math associated to a polyhedron. @cite_6 strengthened and extended the Dyer and Frieze upper bound @cite_22 holding for totally unimodular case; i.e., when @math . Complexity analyses based on @math for the shadow vertex algorithm and the primal-simplex based Tardos' algorithm were proposed by Dadush and H " a hnle @cite_12 , and Mizuno, Sukegawa, and Deza @cite_21 @cite_7 , respectively.
@cite_22 @cite_7 @cite_21 @cite_6 @cite_12
1987985110 1758756115 2005598280 2097442471
We derive a new upper bound on the diameter of a polyhedron @math P = x ? R n : A x  b , where @math A ? Z m  n . The bound is polynomial in @math n and the largest absolute value of a sub-determinant of @math A , denoted by @math  . More precisely, we show that the diameter of @math P is bounded by @math O (  2 n 4 log n  ) . If @math P is bounded, then we show that the diameter of @math P is at most @math O (  2 n 3.5 log n  ) . For the special case in which @math A is a totally unimodular matrix, the bounds are @math O ( n 4 log n ) and @math O ( n 3.5 log n ) respectively. This improves over the previous best bound of @math O ( m 16 n 3 ( log m n ) 3 ) due to Dyer and Frieze (Math Program 64:1---16, 1994). We show that the shadow vertex algorithm can be used to compute a short path between a given pair of vertices of a polytope @math along the edges of P, where Am n. Both, the length of the path and the running time of the algorithm, are polynomial in m, n, and a parameter 1  that is a measure for the flatness of the vertices of P. For integer matrices Am n we show a connection between  and the largest absolute value  of any sub-determinant of A, yielding a bound of O(4mn4) for the length of the computed path. This bound is expressed in the same parameter  as the recent non-constructive bound of O(2n4 log(n )) by [1]. For the special case of totally unimodular matrices, the length of the computed path simplifies to O(mn4), which significantly improves the previously best known constructive bound of O(m16n3 log3 (mn)) by Dyer and Frieze [7]. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . In the mid-eighties Tardos proposed a strongly polynomial algorithm for solving linear programming problems for which the size of the coefficient matrix is polynomially bounded in the dimension of the input. Combining Orlin's primal-based modification and Mizuno's use of the simplex method, we introduce a modification of Tardos' algorithm considering only the primal problem and using the simplex method to solve the auxiliary problems. The proposed algorithm is strongly polynomial if the coefficient matrix is totally unimodular and the auxiliary problems are non-degenerate. Purpose  The purpose of this paper is to suggest an alternative to the widely used Times Cited criterion for analysing citation networks. The approach involves taking account of the natures of the papers that cite a given paper, so as to differentiate between papers that attract the same number of citations.Design methodology approach  ArticleRank is an algorithm that has been derived from Google's PageRank algorithm to measure the influence of journal articles. ArticleRank is applied to two datasets  a citation network based on an early paper on webometrics, and a selfcitation network based on the 19 most cited papers in the Journal of Documentation  using citation data taken from the Web of Knowledge database.Findings  ArticleRank values provide a different ranking of a set of papers from that provided by the corresponding Times Cited values, and overcomes the inability of the latter to differentiate between papers with the same numbers of citations. The difference in rankings between Times Cited ...