Publication

Extended Formulations from Communication Protocols in Output-Efficient Time

Related publications (36)

Graph Chatbot

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.

0/1 vertex and facet enumeration with BDDs

Friedrich Eisenbrand

In polyhedral studies of 0/1 polytopes two prominent problems exist. One is the vertex enumeration problem: Given a system of inequalities, enumerate its feasible 0/1 points. Another one is the convex hull problem: Given a set of 0/1 points in dimension d, ...

2007

f-vectors of Minkowski additions of convex polytopes

Christophe Weibel

The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and the combinatorial properties of the Minkowski sum with their own dual. In p ...

2007

A conjecture about Minkowski additions of convex polytopes

Christophe Weibel

This is a short paper on different proofs for special cases of a conjecture about Minkowski sums of polytopes. ...

2006

Generalized vertex coloring problems using split graphs

Tinaz Ekim

Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. ...

EPFL2006

Computing faces up to k dimensions of a Minkowski sum of polytopes

Christophe Weibel

We consider the problem of listing faces of the Minkowski sum of several V-polytopes in R^d. An algorithm for listing all faces of dimension up to j is presented, for any given 0

2005

Polyhedral Tools for Control

Colin Neil Jones

Polyhedral operations play a central role in constrained control. One of the most fundamental operations is that of projection, required both by addition and multiplication. This thesis investigates projection and its relation to multi-parametric linear op ...

University of Cambridge2005

Computation of Observability Regions for Piecewise Affine Systems: A Projection-Based Algorithm

Giancarlo Ferrari Trecate

In this paper we consider the problem of computing sets of observable states for discrete-time, piecewise affine systems. When the maximal set of observable states is full-dimensional, we provide an algorithm for reconstructing it up to a zero measure set. ...

2005

On the stable set polytope of claw-free graphs

Gautier Stauffer

In this thesis we focus our attention on the stable set polytope of claw-free graphs. This problem has been open for many years and albeit all the efforts engaged during those last three years, it is still open. This does not mean that no progress has been ...

EPFL2005

Equality Set Projection: A new algorithm for the projection of polytopes in halfspace representation

Colin Neil Jones

In this paper we introduce a new algorithm called Equality Set Projection (ESP) for computing the orthogonal projection of bounded, convex polytopes. Our solution addresses the case where the input polytope is represented as the intersection of a finite nu ...

Cambridge University Engineering Dept2004

Extended convex hull

Thomas Liebling

In this paper we address the problem of computing a minimal representation of the convex hull of the union of k H- polytopes in . Our method applies the reverse search algorithm to a shelling ordering of the facets of the convex hull. Efficient wrapping is ...

2001