scientific article

Publication date: 1986

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

Bounding basis reduction properties, Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance, Note on shortest and nearest lattice vectors, Computational complexity of inner and outer $j$-radii of polytopes in finite-dimensional normed spaces, A geometric inequality and the complexity of computing volume, Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction, Mathematical Programming Models and Exact Algorithms, On the complexity of some basic problems in computational convexity. I. Containment problems, Computing the volume is difficult, On minimizing the largest eigenvalue of a symmetric matrix, Games of fixed rank: a hierarchy of bimatrix games, Lattice based extended formulations for integer linear equality systems, Convex hulls, oracles, and homology, Improving the efficiency of the branch and bound algorithm for integer programming based on ``flatness information, On the Efficacy of Solving LWE by Reduction to Unique-SVP, Comment on: ``Approximation algorithms for quadratic programming, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms, GRIN: An implementation of Gröbner bases for integer programming, Blocking duality for $p$-modulus on networks and applications, A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints, 0/1-Integer programming: Optimization and Augmentation are equivalent, Subfield attacks on HSVP in ideal lattices, Complexity of optimizing over the integers, Improving convergence and practicality of slide-type reductions, Gradual sub-lattice reduction and a new complexity for factoring polynomials, Super-Golden-Gates for $PU(2)$, The planar $k$-means problem is NP-hard, An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths, Approximating the SVP to within a factor $(1+1/\dim^\varepsilon)$ is NP-hard under randomized reductions, The Collatz-Wielandt quotient for pairs of nonnegative operators., Chvátal closures for mixed integer programming problems, Jug measuring: algorithms and complexity, On the number of lattice free polytopes, The complexity of controlled selection, Finding smooth integers in short intervals using CRT decoding, The symbiotic relationship of combinatorics and matrix theory, LLL for ideal lattices: re-evaluation of the security of Gentry-Halevi's FHE scheme, Rational orthogonal approximations to orthogonal matrices, Approximation algorithms for indefinite quadratic programming, Concave extensions for nonlinear 0-1 maximization problems, Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices, Non-standard approaches to integer programming, On a transfer theorem for the $\text{P}\neq \text{NP}$ conjecture, Fast LLL-type lattice reduction, Short Bases of Lattices over Number Fields, Hermite’s Constant and Lattice Algorithms, LLL: A Tool for Effective Diophantine Approximation, On the complexity of cutting-plane proofs, On finite-precision representations of geometric objects, A Digital Signature Scheme Based on CVP ∞, An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution, A survey on graphs with convex quadratic stability number, Predicting Lattice Reduction, On sparse reflexive generalized inverse, The Santalo point of a planar convex set, A random polynomial time algorithm for well-routing convex bodies, The Fast Cauchy Transform and Faster Robust Linear Regression, Sampling methods for shortest vectors, closest vectors and successive minima, Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation, A $2^{n/2}$-time algorithm for $\sqrt{n} $-SVP and $\sqrt{n} $-Hermite SVP, and an improved time-approximation tradeoff for (H)SVP, On the ideal shortest vector problem over random rational primes, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, The convergence of slide-type reductions, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, An FPTAS for the volume of some $\mathcal{V} $-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes, Approximation algorithms for covering/packing integer programs, Bicliques and eigenvalues, Slide reduction, revisited -- filling the gaps in SVP approximation, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, The maximum clique problem, Forty years of attacks on the RSA cryptosystem: A brief survey