15 citations · 45 across the 5 of their papers we have counts for
6 papers
Sherali-Adams Relaxations of Graph Isomorphism Polytopes
Peter N. Malkin
We investigate the Sherali-Adams lift & project hierarchy applied to a graph isomorphism polytope whose integer points encode the isomorphisms between two graphs. In particular, th…
Recognizing Graph Theoretic Properties with Polynomial Ideals
J. A. De Loera, C. Hillar, P. N. Malkin +1
Many hard combinatorial problems can be modeled by a system of polynomial equations. N. Alon coined the term polynomial method to describe the use of nonlinear polynomials when sol…
Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization
Jesus A. De Loera, Peter N. Malkin, Pablo A. Parrilo
The purpose of this note is to survey a methodology to solve systems of polynomial equations and inequalities. The techniques we discuss use the algebra of multivariate polynomials…
Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
J. A. De Loera, J. Lee, P. Malkin +1
Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e…
Truncated Markov bases and Gröbner bases for Integer Programming
Peter N. Malkin
We present a new algorithm for computing a truncated Markov basis of a lattice. In general, this new algorithm is faster than existing methods. We then extend this new algorithm so…
Computing generating sets of lattice ideals
Raymond Hemmecke, Peter Malkin
In this article, we present a new algorithm for computing a generating set of a lattice ideal. This algorithm is based on a project-and-lift approach and is implemented in 4ti2. We…