Publication:3745276
From MaRDI portal
zbMath0606.68039MaRDI QIDQ3745276
Publication date: 1986
combinatorial optimization; flow problems; polynomial algorithms; geometry of numbers; ellipsoid method; integer programming in a fixed dimension; minimization of submodular functions; n-dimensional convex sets; optimization in perfect graphs; shallow cuts; simultaneous diophantine approximation algorithm
68Q25: Analysis of algorithms and problem complexity
90C10: Integer programming
68R10: Graph theory (including graph drawing) in computer science
52A20: Convex sets in (n) dimensions (including convex hypersurfaces)
Related Items
On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines, A Digital Signature Scheme Based on CVP ∞, Predicting Lattice Reduction, Finding smooth integers in short intervals using CRT decoding, On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture, On the complexity of cutting-plane proofs, On finite-precision representations of geometric objects, Rational orthogonal approximations to orthogonal matrices, Approximation algorithms for indefinite quadratic programming, Concave extensions for nonlinear 0-1 maximization problems, Non-standard approaches to integer programming, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Improving the efficiency of the branch and bound algorithm for integer programming based on ``flatness information, Chvátal closures for mixed integer programming problems, Jug measuring: algorithms and complexity, A geometric inequality and the complexity of computing volume, Computing the volume is difficult, The complexity of controlled selection, The symbiotic relationship of combinatorics and matrix theory, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, The maximum clique problem, On the complexity of some basic problems in computational convexity. I. Containment problems, On minimizing the largest eigenvalue of a symmetric matrix, The Santalo point of a planar convex set, A random polynomial time algorithm for well-routing convex bodies, Bicliques and eigenvalues, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions, On the number of lattice free polytopes, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, Fast LLL-type lattice reduction, Approximation algorithms for covering/packing integer programs, Convex hulls, oracles, and homology
