Concept
Schéma d'approximation en temps polynomial
Publications associées (278)
Approximation Algorithms for Allocation and Network Design
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 ...
EPFL2023Structural impact of the start-up sequence on Pelton turbines lifetime: Analytical prediction and polynomial optimization
Mario Paolone, Elena Vagnoni, Aldo Leonardo Alerci
Hydropower plants play a crucial role in the power system facing ambitious renewable energy targets. Due to their inherent controllability, they are well suited to provide flexibility to the grid. However, an increased flexibility provision leads to a prol ...
2023Results 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 p ...
EPFL2023Certification of Bottleneck Task Assignment With Shortest Path Criteria
Maryam Kamgarpour, Tony Alan Wood
Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...
2023The dynamics of unsteady frictional slip pulses
Thibault Didier Roch, Fabian Barras
Self-healing slip pulses are major spatiotemporal failure modes of frictional systems, featuring a characteristic size L(t) and a propagation velocity c(p)(t) (t is time). Here, we develop a theory of slip pulses in realistic rate- and state-dependent fric ...
Washington2023Streaming and Matching Problems with Submodular Functions
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