Publication

The School Bus Problem on Trees

Publications associées (32)

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

Assoc Computing Machinery2023

Nonlocally-resonant metamaterials

Aleksi Antoine Bossart

In this thesis, we unveil a third design path to manipulate elastic waves within architected media, distinct from the traditional phononic crystal and locally-resonant metamaterial concepts. The core innovation lies in the concept of nonlocal resonances, d ...

EPFL2023

Bootstrapping traceless symmetric O(N) scalars

Alessandro Vichi, Maria Refinetti, Marten Jan Reehorst

We use numerical bootstrap techniques to study correlation functions of traceless sym-metric tensors of O(N) with two indices ti j. We obtain upper bounds on operator dimen-sions for all the relevant representations and several values of N. We discover sev ...

SCIPOST FOUNDATION2023

Graphical solutions to one-phase free boundary problems

Xavier Fernandez-Real Girona, Hui Yu

We study viscosity solutions to the classical one-phase problem and its thin counterpart. In low dimensions, we show that when the free boundary is the graph of a continuous function, the solution is the half-plane solution. This answers, in the salient di ...

Walter De Gruyter Gmbh2023

Quality-Constrained Encoding Optimization for Omnidirectional Video Streaming

Pascal Frossard, Roberto Gerson De Albuquerque Azevedo, Chaofan He

Omnidirectional video streaming is usually implemented based on the representations of tiles, where the tiles are obtained by splitting the video frame into several rectangular areas and each tile is converted into multiple representations with different r ...

Ieee-Inst Electrical Electronics Engineers Inc2023

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

Baiwei Guo

Control systems operating in real-world environments often face disturbances arising from measurement noise and model mismatch. These factors can significantly impact the perfor- mance and safety of the system. In this thesis, we aim to leverage data to de ...

EPFL2023

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Mehmet Fatih Sahin

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

EPFL2023

Time vs. Truth: Age-Distortion Tradeoffs and Strategies for Distributed Inference

Yunus Inan

In 1948, Claude Shannon laid the foundations of information theory, which grew out of a study to find the ultimate limits of source compression, and of reliable communication. Since then, information theory has proved itself not only as a quest to find the ...

EPFL2023

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

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