Publication

New Results in the Theory of Linear and Integer Programming

Related publications (261)

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.

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] ...

Assoc Computing Machinery2016

From Massive Parallelization to Quantum Computing: Seven Novel Approaches to Query Optimization

Immanuel Trummer

The goal of query optimization is to map a declarative query (describing data to generate) to a query plan (describing how to generate the data) with optimal execution cost. Query optimization is required to support declarative query interfaces. It is a co ...

EPFL2016

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

Pattern formation with voluminous processes

Alexandre David Olivier Maurer

When a shoal of small fishes notices a predator, they typically change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. This motivates us to design algorithms with similar properties. In this p ...

EPFL2016

Passenger Centric Train Timetabling Problem

Michel Bierlaire, Shadi Sharif Azadeh, Mohammad Yousef Maknoon, Tomas Robenek

The aim of this paper is to analyze and to improve the current planning process of the passenger railway service in light of the recent railway market changes. In order to do so, we introduce the Passenger Centric Train Timetabling Problem. The originality ...

Pergamon-Elsevier Science Ltd2016

Inventory routing with non-stationary stochastic demands

Michel Bierlaire, Sacha Varone, Mohammad Yousef Maknoon, Iliya Dimitrov Markov

We solve a rich logistical problem inspired from practice, in which a heterogeneous fixed fleet of vehicles is used for collecting recyclable waste from large containers over a finite planning horizon. Each container is equipped with a sensor, which commun ...

2016

A New Framework for Distributed Submodular Maximization

Justin Dean Ward

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distributed algo ...

Ieee2016

Considerations for Rank-based Cryptosystems

Anna-Lena Horlemann, Joachim Rosenthal

Cryptosystems based on rank metric codes have been considered as an alternative to McEliece cryptosystems due to the relative difficulty of solving the rank syndrome decoding problem. Generic attacks have recently seen several improvements, notably in the ...

Ieee2016

Submodular Stochastic Probing on Matroids

Justin Dean Ward, Marek Adamczyk

In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Mo ...

INFORMS2016

Tracking Interacting Objects Using Intertwined Flows

Pascal Fua, François Fleuret, Engin Türetken, Xinchao Wang

In this paper, we show that tracking different kinds of interacting objects can be formulated as a network-flow Mixed Integer Program. This is made possible by tracking all objects simultaneously using intertwined flow variables and expressing the fact tha ...

Institute of Electrical and Electronics Engineers2016