Publication

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Ola Nils Anders Svensson, Abbas Bazzi
2018
Journal Articles

Abstract

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear programming (LP) relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. In this paper we address this issue and obtain LP relaxations of quasi-polynomial size that are at least as strong as that given by the knapsack cover inequalities.

Official source

https://infoscience.epfl.ch/entities/publication/41ca90e3-607a-46cc-85d9-ab503cfdd77b

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Chat with Graph Search

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

Supercritical Tradeoffs for Monotone Circuits

Learning to Reason with Neural Networks: Principles and Methods