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

Related publications (25)

Results on Sparse Integer Programming and Geometric Independent Sets

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Sensitivity to user mischaracterizations in electric vehicle charging

Nils Gustav Nilsson

In this paper, we consider electric vehicle charging facilities that offer various levels of service, i.e., charging rates, for varying prices such that rational users choose a level of service that minimizes the total cost to themselves including an oppor ...

ELSEVIER2023

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

Systematic benchmarking of single-cell ATAC-sequencing protocols

Bart Deplancke, Jörn Pezoldt, Camille Lucie Germaine Lambert

Benchmarking of scATAC-seq protocols demonstrates the effects of data quality on downstream analyses. ...

NATURE PORTFOLIO2023

Fairness and Explainability in Clustering Problems

Xinrui Jia

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

EPFL2023

Hardware-Software co-design Methodologies for Edge AI Optimization

Flavio Ponzina

ML-based edge devices may face memory and computational errors that affect applications' reliability and performance. These errors can be the result of particular working conditions (e.g., radiation areas in physical experiments or avionics) or could be th ...

EPFL2023

Optimal Matching of Random Parts

Thomas Alois Weber

This paper examines the minimization of the cost for an expected random production output, given an assembly of finished goods from two random inputs, matched in two categories. We describe the optimal input portfolio, first using the standard normal appro ...

2022

Modeling and mitigating supply chain disruptions as a bilevel network flow problem

Ralf Seifert, Anna Timonina-Farkas, René Yves Glogg

Years of globalization, outsourcing and cost cutting have increased supply chain vulnerability calling for more effective risk mitigation strategies. In our research, we analyze supply chain disruptions in a production setting. Using a bilevel optimization ...

2022

The evolution of triphenylamine hole transport materials for efficient perovskite solar cells

Mohammad Khaja Nazeeruddin

In recent years, the dramatic increase in power conversion efficiency (PCE) coupled with a decrease in the total cost of third-generation solar cells has led to a significant increase in the collaborative research efforts of academic and industrial researc ...

Royal Society of Chemistry2022

Exergy and exergoeconomic analyses of sustainable furfural production via reactive distillation

François Maréchal

Lignocellulosic biomass is a potential renewable resource for production of high-value, sustainable products. Furfural is among the important bio-based chemicals in biorefineries. However, the conventional process of furfural production using a reaction-se ...

2021

Modeling Supply Chain Disruptions: A Network Flow Approach

René Yves Glogg

Globalization, outsourcing and cost optimization have all contributed to increased supply chain vulnerability, yet our understanding of effective mitigation strategies remains limited. In our research, we study the effects of disruptions on supply chain ne ...

EPFL2021

Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information

Giuseppe Carleo, Julien Sebastian Gacon

The Quantum Fisher Information matrix (QFIM) is a central metric in promising algorithms, such as Quantum Natural Gradient Descent and Variational Quantum Imaginary Time Evolution. Computing the full QFIM for a model with d parameters, however, is computat ...

VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF2021

Advantages of patient-specific cutting guides with disposable instrumentation in total knee arthroplasty: a case control study

Brigitte Jolles-Haeberli

BackgroundTotal knee arthroplasty (TKA) is most frequently planned using conventional two-dimensional weight-bearing lower limb radiographs and is performed with conventional femoral and tibial cutting guides. Questions have been raised about the accuracy ...

BMC2021

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

ASSOC COMPUTING MACHINERY2021

Towards a sustainable supply chain on plastic waste management : a multi-criteria optimization approach

François Maréchal, Ivan Daniel Kantor, Rafael Amorim Leandro De Castro Amoedo

Municipal solid waste and waste plastics are currently perceived as an environmental threat. Thermovalorization and recycling are the primary technologies used for disposal, with re- searchers and practitioners advocating for one or the other, but far from ...

2021

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Friedrich Eisenbrand, Moritz Andreas Venzin, Jana Tabea Cslovjecsek

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021

A numerical algorithm based on probing to find optimized transmission conditions

Tommaso Vanzan

Optimized Schwarz Methods (OSMs) are based on optimized transmission conditions along the interfaces between the subdomains. Optimized transmission conditions are derived at the theoretical level, using techniques developed in the last decades. The hypothe ...

Springer-Verlag2023

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Ola Nils Anders Svensson, Moran Feldman, Ashkan Norouzi Fard

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model t ...

ASSOC COMPUTING MACHINERY2020

Multi-objective optimization and exergoeconomic analysis of a continuous solar-driven system with PCM for power, cooling and freshwater production

Hossein Pourrahmani

In this article, three different modes of a novel integrated system would be evaluated by the application of high temperature Thermal Energy Storage (TES) to produce electricity, cooling, and freshwater. Freshwater is produced using the reverse osmosis (RO ...

Elsevier2020

Local approximation of the Maximum Cut in regular graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

ELSEVIER2020