Minkowski's Convex Body Theorem and Integer Programming
From MaRDI portal
Publication:3780763
DOI10.1287/moor.12.3.415zbMath0639.90069OpenAlexW2026129593WikidataQ94973792 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
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, Meta-heuristic approaches to solve shortest lattice vector problem, New Algorithmic Results for Bin Packing and Scheduling, Parameterized Resiliency Problems via Integer Linear Programming, About the Complexity of Two-Stage Stochastic IPs, The Integrality Number of an Integer Program, Partially Known Nonces and Fault Injection Attacks on SM2 Signature Algorithm, Harmonious Coloring: Parameterized Algorithms and Upper Bounds, Enumerating Integer Points in Polytopes with Bounded Subdeterminants, Recovering zeros of polynomials modulo a prime, On the Efficacy of Solving LWE by Reduction to Unique-SVP, Local Testing of Lattices, A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs, The complexity of speedrunning video games, A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors, Algorithmic Applications of Tree-Cut Width, Grundy Distinguishes Treewidth from Pathwidth, Lattice Point Enumeration on Block Reduced Bases, An algorithmic framework for locally constrained homomorphisms, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, On data reduction for dynamic vector bin packing, Lifts for Voronoi cells of lattices, Dynamic coloring on restricted graph classes, Sieve algorithms for some orthogonal integer lattices, Building large \(k\)-cores from sparse graphs, Individual discrete logarithm with sublattice reduction, From approximate to exact integer programming, Reconstructing points of superelliptic curves over a prime finite field, Fair and efficient allocation with few agent types, few item types, or small value levels, Revisiting the Sparsification Technique in Kannan’s Embedding Attack on LWE, An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints, Packing arc-disjoint cycles in oriented graphs, Block-structured integer programming: can we parameterize without the largest coefficient?, On structural parameterizations of star coloring, Structural parameterization of alliance problems, A multivariate complexity analysis of the material consumption scheduling problem, Block Reduced Lattice Bases and Successive Minima, Development and analysis of massive parallelization of a lattice basis reduction algorithm, Critical properties of bipartite permutation graphs, On coresets for fair clustering in metric and Euclidean spaces and their applications, Grid recognition: classical and parameterized computational perspectives, A survey on single server private information retrieval in a coding theory perspective, Complexity of optimizing over the integers, On the optimality of pseudo-polynomial algorithms for integer programming, Efficient Modular Arithmetic in Adapted Modular Number System Using Lagrange Representation, Balanced connected partitions of graphs: approximation, parameterization and lower bounds, Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs, Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems, On fluxes in the \(1^9\) Landau-Ginzburg model, Extended MSO model checking via small vertex integrity, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Parameterized Complexity of Safe Set, An improved method for predicting truncated multiple recursive generators with unknown parameters, Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP), Lattice-based locality sensitive hashing is optimal, An Experimental Study of Kannan’s Embedding Technique for the Search LWE Problem, Approximate CVP_p in Time 2^{0.802 n}, Faster Algorithms for Integer Programs with Block Structure, Algorithms for the Shortest and Closest Lattice Vector Problems, Integer Programming in Parameterized Complexity: Three Miniatures., On the Optimality of Pseudo-polynomial Algorithms for Integer Programming, Centerpoints: A Link between Optimization and Convex Geometry, Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, Predicting nonlinear pseudorandom number generators, Hermite’s Constant and Lattice Algorithms, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, The Cutting Plane Method is Polynomial for Perfect Matchings, Exact algorithms for weighted and unweighted Borda manipulation problems, NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs, On the integrality gap of binary integer programs with Gaussian data, Parameterized complexity of satisfactory partition problem, Graph square roots of small distance from degree one graphs, Algorithms for Controlling Palletizers, Capital Budgeting Problems: A Parameterized Point of View, Exploring the gap between treedepth and vertex cover through vertex integrity, Unnamed Item, A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge, On compact representations of Voronoi cells of lattices, Subgraph isomorphism on graph classes that exclude a substructure, On the integrality gap of binary integer programs with Gaussian data, An EPTAS for scheduling on unrelated machines of few different types, Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle, Closing the Gap for Makespan Scheduling via Sparsification Techniques, About the Structure of the Integer Cone and Its Application to Bin Packing, Parameterized Complexity Results for 1-safe Petri Nets, Parallel Implementation of BDD Enumeration for LWE, On Integer Programming and Convolution., A Multivariate Approach for Checking Resiliency in Access Control, Algorithmic Applications of Tree-Cut Width, Cryptography Based on Quadratic Forms: Complexity Considerations, Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors, Offensive alliances in graphs, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming, SLIDE REDUCTION, SUCCESSIVE MINIMA AND SEVERAL APPLICATIONS
