Publication

CoPhy: A Scalable, Portable, and Interactive Index Advisor for Large Workloads

Publications associées (16)

Multi-robot task allocation for safe planning against stochastic hazard dynamics

We address multi-robot safe mission planning in uncertain dynamic environments. This problem arises in several applications including safety-critical exploration, surveillance, and emergency rescue missions. Computation of a multi-robot optimal control pol ...

IEEE2023

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Discrete Optimal Transport with Independent Marginals is #P-Hard

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

2023

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

Online parallel coordinates tool for optimal utility design in the dairy industry

François Maréchal, Maziar Kermani, Anna Sophia Wallerand, Ivan Daniel Kantor

Despite commonly reported potentials for emission reduction and efficiency increase, industrial heat pumps have yet to reach wide-scale employment in non-refrigeration appli- cations. The bottlenecks are identified as a general scepticism from process oper ...

2018

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

LPN in Cryptography : an Algorithmic Study

Sonia Mihaela Bogos

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

EPFL2017

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

NoDB: Efficient Query Execution on Raw Data Files

Anastasia Ailamaki, Ioannis Alagiannis, Renata Borovica-Gajic, Miguel Sérgio De Oliveira Branco

As data collections become larger and larger, users are faced with increasing bottlenecks in their data analysis. More data means more time to prepare and to load the data into the database before executing the desired queries. Many applications already av ...

Assoc Computing Machinery2015

Query management system and engine allowing for efficient query execution on raw details

Anastasia Ailamaki, Ioannis Alagiannis, Renata Borovica-Gajic, Miguel Sérgio De Oliveira Branco

A database system maintains a feature set of a modern database system while operating directly on raw data files. Systems may use an adaptive indexing mechanism that maintains positional information to provide efficient access to raw data files, a flexible ...

2014

Pliable Index Coding

Christina Fragouli, Siddhartha Brahma

We propose a new formulation of the index coding problem, where instead of demanding a specific message, clients are “pliable” and are happy to receive any one message they do not have. We prove that with this relaxation, although some instances of this pr ...

Ieee2012

The TA2 Database – A Multi-Modal Database From Home Entertainment

Petr Motlicek, Danil Korchagin

This paper presents a new database containing high-definition audio and video recordings in a rather unconstrained video-conferencing-like environment. The database consists of recordings of people sitting around a table in two separate rooms communicating ...

2012

Compression with Graphical Constraints: An Interactive Browser

Amin Karbasi, Morteza Zadimoghaddam

We study the problem of navigating/searching through a database of objects with potentially different popularities using a membership oracle. The membership oracle, given a subset of objects

A

, and a target object

t

, determines whether

A

contains

t

...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

M-DPOP: Faithful distributed implementation of efficient social choice problems

Boi Faltings, Adrian Petcu, David C. Parkes

In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In th ...

2008

Efficient Use of the Query Optimizer for Automated Database Design

Anastasia Ailamaki, Debabrata Dash

State-of-the-art database design tools rely on the query optimizer for comparing between physical design alternatives. Although it provides an appropriate cost model for physical design, query optimization is a computationally expensive process. The signif ...

2007