Publication

An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem

Publications associées (25)

Adaptive algorithms for two fluids flows with anisotropic finite elements and order two time discretizations

This thesis is devoted to the derivation of a posteriori error estimates for the numerical approximation of fluids flows separated by a free surface. Based on these estimates, error indicators are introduced and adaptive algorithms are proposed to solve th ...

EPFL2020

Are renewables really that expensive? The impact of uncertainty on the cost of the energy transition

François Maréchal, Stefano Moret, Francesco Baldi, Xiang Li

The dramatic evidence of climate change is making the transition to more renewable energy systems an urgent global priority. As energy planners normally look 20-50 years ahead, it is crucial to consider the key uncertainties stemming from inaccurate foreca ...

ELSEVIER SCIENCE BV2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Incorporating Location Aspects in Process Integration Methodology

François Maréchal, Hür Ebuzer Bütün, Ivan Daniel Kantor

The large potential for waste resource and heat recovery in industry has been motivating research toward increasing efficiency. Process integration methods have proven to be effective tools in improving industrial sites while decreasing their resource and ...

2019

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