Integer Programming with a Fixed Number of Variables
From MaRDI portal
Publication:3037135
DOI10.1287/moor.8.4.538zbMath0524.90067OpenAlexW2114616381WikidataQ29040555 ScholiaQ29040555MaRDI QIDQ3037135
Publication date: 1983
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.8.4.538
polynomial algorithminteger linear programminggeometry of numbersbasis reduction algorithmNP- completenessfixed number of variables
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05)
Related Items
Polyhedral omega: a new algorithm for solving linear Diophantine systems, An algorithm reminiscent of Euclidean-gcd for computing a function related to pinwheel scheduling, Transversal numbers over subsets of linear spaces, Subadditive approaches in integer programming, On Dedekind's problem for complete simple games, Harmonious coloring: parameterized algorithms and upper bounds, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Studies in Computational Aspects of Voting, Harmonious Coloring: Parameterized Algorithms and Upper Bounds, On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming, Centerpoints: A Link Between Optimization and Convex Geometry, Deciding Emptiness of the Gomory-Chvátal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point, Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures, Complexity of integer quasiconvex polynomial optimization, Effective lattice point counting in rational convex polytopes, Data-complexity of the two-variable fragment with counting quantifiers, Local cuts for mixed-integer programming, Minimum dimensional Hamming embeddings, Unnamed Item, A note on the concrete hardness of the shortest independent vector in lattices, About the decidability of polyhedral separability in the lattice \(\mathbb {Z}^d\). Recognizing digital polyhedra with a prescribed number of faces, On degree sequence optimization, A note on a variant of the online open end bin packing problem, Complexity and approximability of parameterized MAX-CSPs, Minimum-Cost $$b$$-Edge Dominating Sets on Trees, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, Processing succinct matrices and vectors, Classification of annotation semirings over containment of conjunctive queries, No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines, Property Testing for Bounded Degree Databases, Parameterized complexity of distance labeling and uniform channel assignment problems, Algorithmic Applications of Tree-Cut Width, On the Complexity of Wafer-to-Wafer Integration, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, A unified framework for designing EPTAS for load balancing on parallel machines, Privacy in Elections: k-Anonymizing Preference Orders, Estimation of the hardness of the learning with errors problem with a restricted number of samples, Integer programming in parameterized complexity: five miniatures, Robust minimum cost flow problem under consistent flow constraints, A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\), Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives, Computing weakly reversible deficiency zero network translations using elementary flux modes, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, Knapsack problems: a parameterized point of view, Building large \(k\)-cores from sparse graphs, Approximation algorithms for a virtual machine allocation problem with finite types, Fair and efficient allocation with few agent types, few item types, or small value levels, Parameterized complexity of envy-free resource allocation in social networks, On the complexity of quasiconvex integer minimization problem, Block-structured integer programming: can we parameterize without the largest coefficient?, Lower bounds on the size of general branch-and-bound trees, On the optimality of pseudo-polynomial algorithms for integer programming, Alternatives for testing total dual integrality, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Scheduling of pipelined operator graphs, Constructing bounded degree graphs with prescribed degree and neighbor degree sequences, Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey, Helly’s theorem: New variations and applications, On minimum integer representations of weighted games, Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint, Bipartite finite Toeplitz graphs, Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds, Parameterized Dynamic Variants of Red-Blue Dominating Set, Phase transitions in integer linear problems, Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design, An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection, On explaining integer vectors by few homogeneous segments, La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász, A heuristic method for solving integer-valued decompositional multiindex problems, Fast LLL-type lattice reduction, Polynomial algorithms for \(m\times (m+1)\) integer programs and \(m\times (m+k)\) diophantine systems, Parameterized computational complexity of Dodgson and Young elections, On the high multiplicity traveling salesman problem, Multivariate Complexity Analysis of Swap Bribery, The (not so) trivial lifting in two dimensions, Partitioning graphs into induced subgraphs, A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management, On the rational polytopes with Chvátal rank 1, Quantum algorithms for algebraic problems, Conjugacy and Other Properties of One-Relator Groups, Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems, Connectivity and diameter in distance graphs, Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting, Parameterized Complexity Results for 1-safe Petri Nets, Consensus strings with small maximum distance and small distance sum, FPT-algorithm for computing the width of a simplex given by a convex hull, A Multivariate Approach for Checking Resiliency in Access Control, Scheduling meets \(n\)-fold integer programming, Reachability analysis of low-order discrete state reaction networks obeying conservation laws, Low-complexity algorithms for sequencing jobs with a fixed number of job-classes, Integer hulls of linear polyhedra and scl in families, A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops, Parameterized resiliency problems, Exploiting Symmetries in Polyhedral Computations, A computational study of integer programming algorithms based on Barvinok's rational functions, Huge multiway table problems, Parameterized Complexity of Control and Bribery for d-Approval Elections, Combinatorial voter control in elections, Parameterized complexity of control and bribery for \(d\)-approval elections, Meta-heuristic approaches to solve shortest lattice vector problem, Discretely ordered modules as a first-order extension of the cutting planes proof system, New Algorithmic Results for Bin Packing and Scheduling, Parameterized Resiliency Problems via Integer Linear Programming, Iterated Type Partitions, The Integrality Number of an Integer Program, Computing L(p,1)-Labeling with Combined Parameters, Parameterized Complexity of Geodetic Set, Polynomial Time Reachability Analysis in Discrete State Chemical Reaction Networks Obeying Conservation Laws, Enumerating Integer Points in Polytopes with Bounded Subdeterminants, Target Set Selection in Dense Graph Classes, Short Presburger Arithmetic Is Hard, Equivalence of Lattice Orbit Polytopes, Local Testing of Lattices, Multivariable Branching: A 0-1 Knapsack Problem Case Study, Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials, A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs, Rational Modular Encoding in the DCR Setting: Non-interactive Range Proofs and Paillier-Based Naor-Yung in the Standard Model, The Support of Integer Optimal Solutions, Minimization of even conic functions on the two-dimensional integral lattice, Unnamed Item, Grundy Distinguishes Treewidth from Pathwidth, On Lattice Width of Lattice-Free Polyhedra and Height of Hilbert Bases, An algorithmic framework for locally constrained homomorphisms, Branch-and-bound solves random binary IPs in poly\((n)\)-time, A study of lattice reformulations for integer programming, On data reduction for dynamic vector bin packing, Dynamic coloring on restricted graph classes, EPTAS for the dual of splittable bin packing with cardinality constraint, Structural parameterization of cluster deletion, The computational complexity of knot genus in a fixed 3‐manifold, From approximate to exact integer programming, Optimizing low dimensional functions over the integers, Equitable scheduling on a single machine, Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization, The Computational Complexity of Integer Programming with Alternations, EPTAS for parallel identical machine scheduling with time restrictions, Block Reduced Lattice Bases and Successive Minima, Copeland Voting Fully Resists Constructive Control, Parameterized Complexity of Safe Set, Sensitivity theorems in integer linear programming, Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP), Efficient Storage of Pareto Points in Biobjective Mixed Integer Programming, Finding successive minima of an integral lattice and a vector lattice, close to a given one, Constraint Satisfaction Problems over Numeric Domains, Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH, Approximate CVP_p in Time 2^{0.802 n}, Faster Algorithms for Integer Programs with Block Structure, Trichotomy for the reconfiguration problem of integer linear systems, Enumerating Projections of Integer Points in Unbounded Polyhedra, On computations with integer division, Integer Programming in Parameterized Complexity: Three Miniatures., On the Optimality of Pseudo-polynomial Algorithms for Integer Programming, Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs, TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION, Lattice Reformulation Cuts, Robustness among multiwinner voting rules, Centerpoints: A Link between Optimization and Convex Geometry, Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, A natural lattice basis problem with applications, EPTAS for load balancing problem on parallel machines with a non-renewable resource, The History of the LLL-Algorithm, A polynomially solvable special case of the unbounded knapsack problem, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, When can graph hyperbolicity be computed in linear time?, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, 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, Subset Selection in Sparse Matrices, Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids, Graph square roots of small distance from degree one graphs, Exploring the gap between treedepth and vertex cover through vertex integrity, Unnamed Item, Subgraph isomorphism on graph classes that exclude a substructure, On the integrality gap of binary integer programs with Gaussian data, Exploring the gap between treedepth and vertex cover through vertex integrity, An EPTAS for scheduling on unrelated machines of few different types, Closing the Gap for Makespan Scheduling via Sparsification Techniques, About the Structure of the Integer Cone and Its Application to Bin Packing, Deconstructing Intractability: A Case Study for Interval Constrained Coloring, On Integer Programming and Convolution., POLYNOMIAL APPROXIMATION SCHEMES FOR THE MAX-MIN ALLOCATION PROBLEM UNDER A GRADE OF SERVICE PROVISION, Efficient Lattice Width Computation in Arbitrary Dimension, Algorithmic Applications of Tree-Cut Width, Unnamed Item, Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms, Unnamed Item, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming, Knapsack Public Key Cryptosystems and Diophantine Approximation, Variable metric relaxation methods, part II: The ellipsoid method, Parameterized Complexity of Geodetic Set, Computational Short Cuts in Infinite Domain Constraint Satisfaction, Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time, Envy-free allocations respecting social networks, Standard pairs for monomial ideals in semigroup rings, The inapproximability of lattice and coding problems with preprocessing, Energy efficient voltage scheduling for multi-core processors with software controlled dynamic voltage scaling, Covering convex bodies and the closest vector problem, Pisot unit generators in number fields, A general scheme for solving a large set of scheduling problems with rejection in FPT time, Shop scheduling problems with multiprocessor tasks on dedicated processors, Executing join queries in an uncertain distributed environment, Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix, On the harmless set problem parameterized by treewidth, The complexity of vector partition, A parameterized view to the robust recoverable base problem of matroids under structural uncertainty, On lattice point counting in \(\varDelta\)-modular polyhedra, Lattice-free simplices with lattice width \(2d - o(d)\), Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!, Segment LLL reduction of lattice bases using modular arithmetic, Proportionate progress: A notion of fairness in resource allocation, A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables, Short rational generating functions for solving some families of fuzzy integer programming problems, Lattice-based algorithms for number partitioning in the hard phase, Lattice closures of polyhedra, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Parameterized multi-scenario single-machine scheduling problems, Algorithms for highly symmetric linear and integer programs, On the string consensus problem and the Manhattan sequence consensus problem, Super-Golden-Gates for \(PU(2)\), Solving hard stable matching problems involving groups of similar agents, Combinatorial \(n\)-fold integer programming and applications, The maximum deviation just-in-time scheduling problem., On the status sequences of trees, Approximability of scheduling with fixed jobs, Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints, On structural parameterizations of the bounded-degree vertex deletion problem, Thinner is not always better: cascade knapsack problems, On the number of integer points in translated and expanded polyhedra, Multi-attribute proportional representation, Computing \(L(p, 1)\)-labeling with combined parameters, Pattern-guided \(k\)-anonymity, The Small Set Vertex expansion problem, Tropical principal component analysis and its application to phylogenetics, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, Efficient computation of the oriented chromatic number of recursively defined digraphs, On the number of integer points in a multidimensional domain, The projection games conjecture and the hardness of approximation of Super-SAT and related problems, The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints, The complexity landscape of decompositional parameters for ILP, Swapping colored tokens on graphs, Geometric versions of the three-dimensional assignment problem under general norms, Integer programming as projection, An approximation algorithm for box abstraction of transition systems on real state spaces, FPT-algorithms for some problems related to integer programming, Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming, Lattice preconditioning for the real relaxation branch-and-bound approach for integer least squares problems, Parameterized complexity of asynchronous border minimization, Minimum-cost \(b\)-edge dominating sets on trees, A note on non-degenerate integer programs with small sub-determinants, Constant thresholds can make target set selection tractable, Multivariate complexity analysis of Swap Bribery, Algorithmic meta-theorems for restrictions of treewidth, A linear algorithm for integer programming in the plane, Parameterized complexity of \textsc{maximum edge colorable subgraph}, Revenue maximization in Stackelberg pricing games: beyond the combinatorial setting, Integer convex minimization by mixed integer linear optimization, A local maximizer for lattice width of 3-dimensional hollow bodies, Bounding stochastic dependence, joint mixability of matrices, and multidimensional bottleneck assignment problems, Note on the complexity of the mixed-integer hull of a polyhedron, Alliances in graphs of bounded clique-width, Local linear set on graphs with bounded twin cover number, On structural parameterizations of the edge disjoint paths problem, Polyhedral circuits and their applications, On approximation algorithms for concave mixed-integer quadratic programming, The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs, Algorithmic reduction of biological networks with multiple time scales, Approximate CVP\(_p\) in time \(2^{0.802n}\), Cutting-plane proofs in polynomial space, Piecewise linear valued constraint satisfaction problems with fixed number of variables, On the computation of units and class numbers by a generalization of Lagrange's algorithm, Optimization of eigenvalue bounds for the independence and chromatic number of graph powers, The covering radius and a discrete surface area for non-hollow simplices, More on ordered open end bin packing, A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem, On the limits of nonapproximability of lattice problems, Techniques and results on approximation algorithms for packing circles, Target set selection parameterized by vertex cover and more, EPTAS for load balancing problem on parallel machines with a non-renewable resource, Parameterized complexity of maximum edge colorable subgraph, Empowering the configuration-IP: new PTAS results for scheduling with setup times, In memoriam: Gerhard Woeginger (1964--2022), On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates, Computing the covering radius of a polytope with an application to lonely runners, Electing a committee with dominance constraints, Slide reduction, revisited -- filling the gaps in SVP approximation, Random lattices, threshold phenomena and efficient reduction algorithms., A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Short vectors of planar lattices via continued fractions, Modelization of deterministic rational relations, A PTAS for the multiple subset sum problem with different knapsack capacities, The integrality number of an integer program, Packing arc-disjoint cycles in oriented graphs, Parameterized complexity for iterated type partitions and modular-width, Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines, On structural parameterizations of star coloring, Structural parameterization of alliance problems, The possible winner with uncertain weights problem, Enumeration and unimodular equivalence of empty delta-modular simplices, A multivariate complexity analysis of the material consumption scheduling problem, Critical properties of bipartite permutation graphs, On the Column Number and Forbidden Submatrices for \(\Delta\)-Modular Matrices, Disentangling the computational complexity of network untangling, On coresets for fair clustering in metric and Euclidean spaces and their applications, Grid recognition: classical and parameterized computational perspectives, Complexity of optimizing over the integers, A new perspective on single-machine scheduling problems with late work related criteria, On improved interval cover mechanisms for crowdsourcing markets, An approximation algorithm for indefinite mixed integer quadratic programming, Balanced connected partitions of graphs: approximation, parameterization and lower bounds, Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms, Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs, Online minimization of the maximum starting time: migration helps, Robust transshipment problem under consistent flow constraints, An elementary algorithmic problem from an advanced standpoint, Extended MSO model checking via small vertex integrity, Exact Quantization of Multistage Stochastic Linear Problems, Revisiting security estimation for LWE with hints from a geometric perspective, Interactions of computational complexity theory and mathematics, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints, Offensive alliances in graphs, On Lovász' lattice reduction and the nearest lattice point problem, On polynomial kernels for sparse integer linear programs, Vertex cover meets scheduling, New algorithms for minimizing the weighted number of tardy jobs on a single machine, A note on optical routing on trees, Acyclic coloring parameterized by directed clique-width, Parameterized complexity of locally minimal defensive alliances, A fixed point iterative approach to integer programming and its distributed computation, The balanced satisfactory partition problem, Configurations and minority in the string consensus problem, Integer equal flows, Column basis reduction and decomposable knapsack problems, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Complexity of scheduling multiprocessor tasks with prespecified processors allocations, On principal ideal testing in algebraic number fields, Factorization properties of lattices over the integers, Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control, Improved branching disjunctions for branch-and-bound: an analytic center approach, An application of simultaneous diophantine approximation in combinatorial optimization, A hierarchy of polynomial time lattice basis reduction algorithms, Polynomial-time approximation schemes for circle and other packing problems, A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Complexity of Presburger arithmetic with fixed quantifier dimension, Improving the efficiency of the branch and bound algorithm for integer programming based on ``flatness information, A polynomial-time approximation scheme for maximizing the minimum machine completion time, Polynomial kernels for weighted problems, High-multiplicity scheduling on one machine with forbidden start and completion times, Prices matter for the parameterized complexity of shift bribery, Real data-integer solution problems within the Blum-Shub-Smale computational model, Bias expansion of spatial statistics and approximation of differenced lattice point counts, Subclasses of Presburger arithmetic and the polynomial-time hierarchy, The diophantine problem of Frobenius: A close bound, Voting schemes for which it can be difficult to tell who won the election, Testing additive integrality gaps, On variations of the subset sum problem, An approximation scheme for strip packing of rectangles with bounded dimensions, The \(l\)-diversity problem: tractability and approximability, New transference theorems on lattices possessing \(n^\varepsilon\)-unique shortest vectors, Lifting properties of maximal lattice-free polyhedra, Refining the complexity of the sports elimination problem, The complexity of degree anonymization by vertex addition, The optimal LLL algorithm is still polynomial in fixed dimension., \(N\)-fold integer programming and nonlinear multi-transshipment, An approximation scheme for the two-stage, two-dimensional knapsack problem, Trichotomy for integer linear systems based on their sign patterns, Approximability of sparse integer programs, Pattern hit-and-run for sampling efficiently on polytopes, Computing efficiently the lattice width in any dimension, Integer programming, Barvinok's counting algorithm and Gomory relaxations., Splitting full matrix algebras over algebraic number fields., An efficient polynomial time approximation scheme for load balancing on uniformly related machines, A generalization of the integer linear infeasibility problem, An appraisal of computational complexity for operations researchers, The maximum edge-disjoint paths problem in complete graphs, Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods, A randomized sieving algorithm for approximate integer programming, Typechecking top-down XML transformations: Fixed input or output schemas, The minimum feasible tileset problem, Fine covers of a VAS language, Parameterized complexity analysis for the closest string with wildcards problem, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, Unit-time scheduling problems with time dependent resources, Quantifier elimination for modules with scalar variables, On integer points in polyhedra, Pinwheel scheduling with two distinct numbers, The context-freeness of the languages associated with vector addition systems is decidable, \(N\)-fold integer programming, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, Improved approximation algorithms for parallel machine scheduling with release dates and job rejection, Lattice translates of a polytope and the Frobenius problem, Parameterizing by the number of numbers, Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring, Parameterized complexity of coloring problems: treewidth versus vertex cover, Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices, Non-standard approaches to integer programming, A note on scheduling identical coupled tasks in logarithmic time, Branching on general disjunctions, Unbounded knapsack problems with arithmetic weight sequences, Parametric integer programming algorithm for bilevel mixed integer programs, Finding vertex-surjective graph homomorphisms, Integer programming with 2-variable equations and 1-variable inequalities, On the complexity of cutting-plane proofs, Optimal routing in double loop networks, Approximating vector scheduling: almost matching upper and lower bounds, Bin packing with controllable item sizes, Complexity of min-max subsequence problems, Integral infeasibility and testing total dual integrality, Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors, Periodic scheduling with obligatory vacations, Deadlock and liveness characterization for a class of generalized Petri nets, Scheduling parallel machines with inclusive processing set restrictions and job release times, The vertices of the knapsack polytope, Integer programming and cryptography, Simultaneous reduction of a lattice basis and its reciprocal basis, An integral transformation for integer programming problems, Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, A dichotomy for real weighted Holant problems
