The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by n equality constraints in n+d variables, where the variables are constrained to be nonnegative. A variable x_r is called redundant, if after removing its nonnegativity constraint the LP still has the same feasible region. The time needed to solve such an LP is denoted by LP(n,d). It is easy to see that solving n+d LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves n+d linear programs, but each of them has at most s variables, where s is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover - and this is the combinatorial aspect - it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable x_r one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for x_r. In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time of order d (n+d) s^{d-1} LP(s,d) + d s^{d} LP(n,d) to detect all redundancies. In the case where all constraints are in general position, the running time is of order s LP(n,d) + (n+d) LP(s,d), which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements.

In this tutorial, we present a new field of research on implementing exact algorithms in optimization and polyhedral computation in exact (arbitrary precision) arithmetic. Such algorithms including those to solve linear programming and convex hull problems have been implemented mostly with floating-point arithmetic. This new field of developing "exact software" in optimization and polyhedral computation is now at the second stage where new mathematical tools relying on optimization and polyhedral codes are being developed that have not been implemented before. This tutorial is not meant to cover all important developments but to look at some interesting facets.

In this paper, the application of combinatorial geometry to noncoherent multiple-symbol differential detection (MSDD) is considered. The resulting algorithm is referred to as CG-MSDD. Analytical expressions for the complexity of CG-MSDD are derived and it is shown that it is polynomial in the length N of the MSDD observation window if the rank of the N times N channel autocorrelation matrix is fixed, but in fact exponential in N if standard fading models are considered. Compared to popular sphere-decoder based MSDD, CG-MSDD is superior (i) in low-signal-to-noise power ratio (SNR) slow-fading channels as its complexity is independent of the SNR, (ii) as its complexity is constant, i.e., independent of the particular channel and noise realization, and (iii) asymptotically, as its complexity exponent only scales linearly with the bandwidth of the fading process.

In this paper, the application of combinatorial geometry to noncoherent multiple-symbol differential detection (MSDD) is considered. The resulting algorithm is referred to as CG-MSDD. Analytical expressions for both the complexity and the error-rate performance of CG-MSDD are derived and it is shown that its complexity is polynomial in the length N of the MSDD observation window if the rank of the N times N channel autocorrelation matrix is fixed, but in fact exponential in N if standard fading models are considered. Compared to popular sphere-decoder based MSDD, CG-MSDD is superior (i) in low-signal-to-noise power ratio (SNR) slow-fading channels as its complexity is independent of the SNR, (ii) as its complexity is constant, i.e., independent of the particular channel and noise realization, and (iii) asymptotically, as its complexity exponent only scales linearly with the bandwidth of the fading process.

The Gröbner walk is an algorithm for conversion between Gröbner bases for different term orders. It is based on the polyhedral geometry of the Gröbner fan and involves tracking a line between cones representing the initial and target term order. An important parameter is the explicit numerical perturbation of this line. This usually involves both time and space, demanding arithmetic of integers much larger than the input numbers. In this paper we show how the explicit line may be replaced by a formal line using Robbiano’s characterization of group orders on Qn. This gives rise to the generic Gröbner walk involving only Gröbner basis conversion over facets and computations with marked polynomials. The infinite precision integer arithmetic is replaced by term order comparisons between (small) integral vectors. This makes it possible to compute with infinitesimal numbers and perturbations in a consistent way without introducing unnecessary long integers. The proposed technique is closely related to the lexicographic (symbolic) perturbation method used in optimization and computational geometry. We report on an implementation of our algorithm specifically tailored to computations with lattice ideals.

Using deformed products of arrangements, we construct a family of linearprograms with n inequalities in Rd on which, in the worst-case, the least-index criss-cross methodrequires Ω(nd) (for fixed d) pivots to reach optimality.

Every convex polytope can be representedas the intersectionof a finiteset of halfspaccs and as theconvex hull of its vertices.Transforming from the halfspace (respectively vertex) to the vertex (respectively halfspace) representationis called vertex enumeration (respectivelyjhcet enumeration).An open questionis whetherthere is analgorithmfor thesetwoproblems(equivalentby geometric du- ality) thatis polynomial in theinputsize and theoutputsize.In this papr, we extend theknown polynomially solvable classes of polytopes by looking at thedual problems.The dud problem of a vertex (facet, respectively) enumerationproblem is the facet (vertex)enumerationproblem for the same polytope where theinputand output are simply interchanged.For a particularclass of polytopes and a fixed algorithm, one transformationmay be much easier than its dual.In this paper, we propose a new class of algorithmsthattake advantageof this phenomenon.Ltmely speaking,prinra14ual algorithmsuse a solution to the easy direction as an oracle to help solve the seemingly harddkection.

Abstract The Hungarian method is an efficient algorithm for finding a minimal‐cost perfect matching in a weighted bipartite graph. This paper describes an efficient algorithm for finding all minimal‐cost perfect matchings. The computational time required to generate each additional perfect matching is O(n(n + m)), and it requires O(n + m) memory storage. This problem can be solved by algorithms for finding the Kth‐best solution of assignment problems. However, the memory storage required by the known algorithms grows in proportion to K, and, hence, it may grow exponentially in n. So, our specialized algorithm has a considerable advantage in memory requirement over the precious more general algorithms for Kth‐best assignment problems. Here we will show that the enumeration of all minimal‐cost perfect matchings can be reduced to the enumeration of all perfect matchings in some bipartite graph. Therefore, our algorithm can be seen as an algorithm for enumerating all perfect matchings in a given bipartite graph.

We present a new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the enumeration of the vertices of an arrartgement or of a convex polyhedron, in arbitrary dimension.The algorithm has the following properties: (a) No additional storage is required beyond the input dam, (b) The output list produced is frw of duplicates; (c) The algorithm is extremely simple, requires no data structures, and handles all degenerate cases; (d) The running time is output sensitive for nondegenerate inputs; (e) The algorithm is easy to efficiently paraIIeIize.For example, the algorithm finds the v vertices of a polyhedron in R d defined by a non-degenerate system of n inequalities (or dually, the v facets of the convex hull of n points in R ~, where each facet contains exactly d given points) in time O (ndv ) and O (rid) space.The v vertices in a simple arrangement of n hyperplanes in R d can be found in O (n2dv ) time and O (rid) space complexity.The algorithm is based on inverting finite pivot algorithms for linear programming.