Rank Lower Bounds for Generic Cutting-Plane Proof Systems

Event Details
  • Date/Time:
    • Tuesday February 1, 2011
      10:00 am - 11:00 am
  • Location: ISyE Executive classroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: Rank Lower Bounds for Generic Cutting-Plane Proof Systems

Full Summary: No summary paragraph submitted.

TITLE:  Rank Lower Bounds for Generic Cutting-Plane Proof Systems

SPEAKER:  Sebastian Pokutta - faculty candidate


We introduce a natural abstraction of cutting-plane proof systems, which subsumes well-known operators such as Gomory-Chvátal, lift-and-project, Sherali-Adams, Lovász-Schrijver, and split cuts. We exhibit a family of polytopes without integral points contained in the n-dimensional 0/1-cube that has rank Omega(n/ log n) for any proof system in our class. In fact, we show that whenever a specific cutting-plane based proof system has (maximal) rank n
on a particular family of instances, then any cutting-plane proof system in our class has rank Omega(n/ log n) for this family. We also construct a new cutting-plane proof system that has worst-case rank O(n/ log n) for any polytope without integral points, implying that the new universal lower bound is virtually tight.
(joint work with Andreas S. Schulz)


Additional Information

In Campus Calendar

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No categories were selected.
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Jan 5, 2011 - 6:51am
  • Last Updated: Oct 7, 2016 - 9:53pm