Publication

On some problems related to 2-level polytopes

Related publications (73)

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.

Safe Motion Planning against Multimodal Distributions Based on a Scenario Approach

Maryam Kamgarpour

We present the design of a motion planning algorithm that ensures safety for an autonomous vehicle. In particular, we consider a multimodal distribution over uncertainties; for example, the uncertain predictions of future trajectories of surrounding vehicl ...

2022

fGOT: Graph Distances Based on Filters and Optimal Transport

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic, Giovanni Chierchia

Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph dis ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Complexity of linear relaxations in integer programming

Matthias Schymura

For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the relaxation complexity rc(X). This parameter was introduced by Kaibel & Weltge (2015) and captures the ...

2020

Ridesourcing Systems - Simulated Annealing Algorithm for Solving the Matching and Dispatching Problem in Dynamic Large-Scale Settings

Lynn Fayed

Ridesourcing services are gaining gradual hypes with the advancements in mobile internet and technology. The objective of these services is to mainly match and dispatch operating vehicles to waiting requests within a very short duration. The expectations t ...

2020

Extended Formulations from Communication Protocols in Output-Efficient Time

Yuri Faenza, Manuel Francesco Aprile

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the exten ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

Tropical Ehrhart Theory and Tropical Volume

Matthias Schymura, Georg Peter Loho

We introduce a novel intrinsic volume concept in tropical geometry. This is achieved by developing the foundations of a tropical analog of lattice point counting in polytopes. We exhibit the basic properties and compare it to existing measures. Our exposit ...

2019

Construction of Polar Codes With Sublinear Complexity

Rüdiger Urbanke, Seyed Hamed Hassani, Marco Mondelli

Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019