𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity of Positivstellensatz proofs for the knapsack

✍ Scribed by D. Grigoriev

Publisher
Springer
Year
2001
Tongue
English
Weight
302 KB
Volume
10
Category
Article
ISSN
1016-3328

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Complexity of Null- and Positivstellensa
Complexity of Null- and Positivstellensatz proofs
✍ Dima Grigoriev; Nicolai Vorobjov πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 91 KB

We introduce two versions of proof systems dealing with systems of inequalities: Positivstellensatz refutations and Positivstellensatz calculus. For both systems we prove the lower bounds on degrees and lengths of derivations for the example due to Lazard, Mora and Philippon. These bounds are sharp,

On the complexity of cutting-plane proof
On the complexity of cutting-plane proofs
✍ W. Cook; C.R. Coullard; Gy. TurΓ‘n πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 881 KB
Bounds on the size of branch-and-bound p
Bounds on the size of branch-and-bound proofs for integer knapsacks
✍ Bala Krishnamoorthy πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 172 KB

Using a direct counting argument, we derive lower and upper bounds for the number of nodes enumerated by linear programming-based branch-and-bound (B&B) method to prove the integer infeasibility of a knapsack. We prove by example that the size of the B&B tree could be exponential in the worst case.