Title	Bounded pitch inequalities for min knapsack: approximate separation and integrality gaps
Creator	Faenza, Yuri
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2018-09-27T17:01
Description	The pitch of a (valid) inequality for the min knapsack polytope is the minimum integer k such that, if any k variables from its support are set to one, then the inequality is satisfied. Bounded pitch inequalities came to prominence for their connections with the Chvatal-Gomory and Bienstock-Zuckerberg operators. In this talk, we investigate the strength of bounded pitch inequalities, proving bounds on the integrality gap when they are added to the natural LP relaxation (possibly, in conjunction with other inequalities), and we discuss algorithms for approximately separating them.
Extent	30.0 minutes
Subject	Mathematics; Computer science; Operations research, mathematical programming; Operation research
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Columbia University
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2019-04-02
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0377741
URI	http://hdl.handle.net/2429/69399
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Researcher
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos