Minkowski's Convex Body Theorem and Integer Programming
From MaRDI portal
Publication:3780763
DOI10.1287/MOOR.12.3.415zbMath0639.90069DBLPjournals/mor/Kannan87OpenAlexW2026129593WikidataQ94973792 ScholiaQ94973792MaRDI QIDQ3780763
Publication date: 1987
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/925308b01e1a3a9944774a817c63d84c887ee277
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polytopes and polyhedra (52Bxx)
Related Items (only showing first 100 items - show all)
On polynomial kernels for sparse integer linear programs ⋮ Computing the Ehrhart polynomial of a convex lattice polytope ⋮ Dual lattice attacks for closest vector problems (with preprocessing) ⋮ A trace map attack against special ring-LWE samples ⋮ Shortest vectors in lattices of Bai-Galbraith's embedding attack on the LWR problem ⋮ Note on shortest and nearest lattice vectors ⋮ Parameterized complexity of locally minimal defensive alliances ⋮ The balanced satisfactory partition problem ⋮ Column basis reduction and decomposable knapsack problems ⋮ Lattice basis reduction: Improved practical algorithms and solving subset sum problems ⋮ Covering convex bodies and the closest vector problem ⋮ Harmonious coloring: parameterized algorithms and upper bounds ⋮ Solving the search-LWE problem over projected lattices ⋮ An extension of Kannan's embedding for solving ring-based LWE problems ⋮ The hardness of approximate optima in lattices, codes, and systems of linear equations ⋮ On the harmless set problem parameterized by treewidth ⋮ Dual vectors and lower bounds for the nearest lattice point problem ⋮ Polynomial kernels for weighted problems ⋮ Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ A note on the concrete hardness of the shortest independent vector in lattices ⋮ Simultaneously good bases of a lattice and its reciprocal lattice ⋮ Scalable revocable identity-based signature over lattices in the standard model ⋮ List-decoding Barnes-Wall lattices ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ Change-making problems revisited: a parameterized point of view ⋮ Parameterized complexity of configuration integer programs ⋮ Improvements in closest point search based on dual HKZ-bases ⋮ Parameterized complexity of max-lifetime target coverage in wireless sensor networks ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ The \(l\)-diversity problem: tractability and approximability ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Attacking the linear congruential generator on elliptic curves via lattice techniques ⋮ Solving low-density multiple subset sum problems with SVP oracle ⋮ Finding a shortest vector in a two-dimensional lattice modulo m ⋮ Knapsack problems: a parameterized point of view ⋮ Analysis of hidden number problem with hidden multiplier ⋮ Refining the complexity of the sports elimination problem ⋮ On the asymptotic complexity of solving LWE ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Cryptanalysis of the GGH cryptosystem ⋮ Parameterized multi-scenario single-machine scheduling problems ⋮ On the string consensus problem and the Manhattan sequence consensus problem ⋮ On lattice-based algebraic feedback shift registers synthesis for multisequences ⋮ A simple \(OPT+1\) algorithm for cutting stock under the modified integer round-up property assumption ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Recovering a sum of two squares decomposition ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Multi-attribute proportional representation ⋮ A randomized sieving algorithm for approximate integer programming ⋮ The minimum feasible tileset problem ⋮ The Small Set Vertex expansion problem ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ A public-key encryption scheme based on non-linear indeterminate equations ⋮ On integer points in polyhedra ⋮ The complexity landscape of decompositional parameters for ILP ⋮ Swapping colored tokens on graphs ⋮ Lattice translates of a polytope and the Frobenius problem ⋮ Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix ⋮ FPT-algorithms for some problems related to integer programming ⋮ Parallel machine scheduling with speed-up resources ⋮ Parameterized complexity of asynchronous border minimization ⋮ Parameterizing by the number of numbers ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ On explaining integer vectors by few homogeneous segments ⋮ Non-standard approaches to integer programming ⋮ Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices ⋮ Fast LLL-type lattice reduction ⋮ Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms ⋮ Parameterized complexity of \textsc{maximum edge colorable subgraph} ⋮ A local maximizer for lattice width of 3-dimensional hollow bodies ⋮ Alliances in graphs of bounded clique-width ⋮ Optimal routing in double loop networks ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Approximating vector scheduling: almost matching upper and lower bounds ⋮ On the rational polytopes with Chvátal rank 1 ⋮ Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits ⋮ Sampling methods for shortest vectors, closest vectors and successive minima ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Cutting-plane proofs in polynomial space ⋮ Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice ⋮ On the success probability of solving unique SVP via BKZ ⋮ Parameterized resiliency problems ⋮ Parameterized complexity of maximum edge colorable subgraph ⋮ Test sets of integer programs ⋮ Empowering the configuration-IP: new PTAS results for scheduling with setup times ⋮ Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency ⋮ LWE with side information: attacks and concrete security estimation ⋮ Combinatorial voter control in elections ⋮ Towards an algorithmic guide to Spiral Galaxies ⋮ A note on BDD problems with \(\lambda_2\)-gap ⋮ The remote set problem on lattices ⋮ Search for combinatorial objects using lattice algorithms -- revisited ⋮ The integrality number of an integer program ⋮ About the complexity of two-stage stochastic IPs ⋮ New approximability results for two-dimensional bin packing
This page was built for publication: Minkowski's Convex Body Theorem and Integer Programming
