Information theory and polyhedral combinatorics

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 01 Sep 2015Publisher:IEEEJournal:2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)

Authors: Sebastian Pokutta;

doi: 10.1109/allerton.2015.7447134

Information theory and polyhedral combinatorics

- Summary
- Metrics

Abstract

The theory of extended formulations is concerned with the optimal polyhedral representation of a (combinatorial) optimization problem. In this context, information-theoretic methods recently gained significant attention as a convenient way to provide strong lower bounds on the size of such representations. We will provide an introduction to information-theoretic methods in extended formulations, an overview of recent results, and discuss important open problems in extended formulations, which might be amenable to information-theoretic approaches.

Related Organizations

Georgia Institute of Technology
United States

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average