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

Publications associées (32)

À propos
Confidentialité
Mentions légales

Graph Chatbot

On Speed and Advantage : Results in Information Velocity and Monitoring Problems

Reka Inovan

Information theory has allowed us to determine the fundamental limit of various communication and algorithmic problems, e.g., the channel coding problem, the compression problem, and the hypothesis testing problem. In this work, we revisit the assumptions ...

EPFL2024

Energy Management of Price-Maker Community Energy Storage by Stochastic Dynamic Programming

Tianshu Yang, Xue Zhang

In this paper, we propose an analytical stochastic dynamic programming (SDP) algorithm to address the optimal management problem of price-maker community energy storage. As a price-maker, energy storage smooths price differences, thus decreasing energy arb ...

China Electric Power Research Inst2024

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

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

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

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

Certification 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 ...

2023

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

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

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

Maryam Kamgarpour, Orcun Karaca

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

Structural 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 ...

Pergamon-Elsevier Science Ltd2023

Page 2 sur 4

Structural impact of the start-up sequence on Pelton turbines lifetime: Analytical prediction and polynomial optimization

Mario Paolone, Elena Vagnoni, Aldo Leonardo Alerci

Pergamon-Elsevier Science Ltd2023

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Maryam Kamgarpour, Tony Alan Wood

2023