A Polyhedral Characterization of Border Bases
From MaRDI portal
(Redirected from Publication:5744696)
Abstract: Border bases arise as a canonical generalization of Gr"obner bases. We provide a polyhedral characterization of all order ideals (and hence border bases) that are supported by a zero-dimensional ideal: order ideals that support a border basis correspond one-to-one to integral points of the order ideal polytope. In particular, we establish a crucial connection between the ideal and its combinatorial structure. Based on this characterization we adapt the classical border basis algorithm to allow for computing border bases for arbitrary order ideals, which are independent of term orderings. We also show that finding a maximum weight order ideal that supports a border basis is NP-hard, and that the convex hull of admissible order ideals has no polynomial polyhedral description.
Recommendations
- Computing border bases without using a term ordering
- Subideal border bases
- Border basis detection is NP-complete
- Border basis representation of a general quotient algebra
- An algebraist's view on border bases
- Computing border bases
- Complexity of Gröbner basis detection and border basis detection
- Characterizations of border bases
- Computing coupled border bases
- Stable border bases for ideals of points
Cites work
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Polyhedral Characterization of Border Bases
- Algebraic attacks galore!
- An algebraist's view on border bases
- An application of Möller's algorithm to coding theory
- An introduction to statistical learning. With applications in R
- Approximate computation of zero-dimensional polynomial ideals
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Border basis detection is NP-complete
- Border basis relaxation for polynomial optimization
- Characterizations of border bases
- Combinatorial Nullstellensatz
- Complexity of Gröbner basis detection and border basis detection
- Computation with polynomial equations and inequalities arising in combinatorial optimization
- Computing border bases
- Computing border bases without using a term ordering
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Cutting corners
- Deformations of border bases
- Efficient algorithms for solving overdefined systems of multivariate polynomial equations
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Extended formulations in combinatorial optimization
- Generalized normal forms and polynomial system solving
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- scientific article; zbMATH DE number 4076472 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 503184 (Why is no real title available?)
- scientific article; zbMATH DE number 1504686 (Why is no real title available?)
- scientific article; zbMATH DE number 1515218 (Why is no real title available?)
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- scientific article; zbMATH DE number 2206382 (Why is no real title available?)
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Inapproximability of combinatorial problems via small LPs and SDPs
- Linear vs. semidefinite extended formulations
- Maximal Closure of a Graph and Applications to Combinatorial Problems
- On border basis and Gröbner basis schemes
- Recognizing graph theoretic properties with polynomial ideals
- SCIP: solving constraint integer programs
- Stable border bases for ideals of points
- Stable normal forms for polynomial system solving
- Subideal border bases
- The polynomial method and restricted sums of congruence classes
- The traveling salesman problem. A computational study.
Cited in
(17)- On the weak order ideal associated to linear codes
- Complexity of Gröbner basis detection and border basis detection
- Characterizations of border bases
- Computing border bases without using a term ordering
- Computing coupled border bases
- Border basis for polynomial system solving and optimization
- Stable border bases for ideals of numerical Cartesian sets
- Computing border bases using mutant strategies
- Subideal border bases
- Border bases for lattice ideals
- Computing an invariant of a linear code
- Border basis representation of a general quotient algebra
- Border basis detection is NP-complete
- Computing all border bases for ideals of points
- An algebraist's view on border bases
- A Polyhedral Characterization of Border Bases
- Stable border bases for ideals of points
This page was built for publication: A Polyhedral Characterization of Border Bases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5744696)
