Publications associées à k-Edge-Connectivity: Approximation and LP Relaxation

Publications associées (34)

Auto-Bidding in Real-Time Auctions via Oracle Imitation Learning

Online advertising has become one of the most successful business models of the internet era. Impression opportunities are typically allocated through real-time auctions, where advertisers bid to secure advertisement slots. Deciding the best bid for an imp ...

ACM2025

A ride time-oriented scheduling algorithm for dial-a-ride problems

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Pergamon-Elsevier Science Ltd2024

Fly-Swat or Cannon? Cost-Effective Language Model Choice via Meta-Modeling

Robert West, Maxime Jean Julien Peyrard, Marija Sakota

Generative language models (LMs) have become omnipresent across data science. For a wide variety of tasks, inputs can be phrased as natural language prompts for an LM, from whose output the solution can then be extracted. LM performance has consistently be ...

Assoc Computing Machinery2024

Learning to Remove Cuts in Integer Linear Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...

2024

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

Lukas Fritz Felix Vogl

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Paul Scharnhorst

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

EPFL2024

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Colin Peter Sandon

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Nicolas Boumal

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Siam Publications2024

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

Maryam Kamgarpour

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

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

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

Efficient Online Clustering with Moving Costs

Volkan Cevher, Efstratios Panteleimon Skoulakis

In this work we consider an online learning problem, called Online k-Clustering with Moving Costs, at which a learner maintains a set of k facilities over T rounds so as to minimize the connection cost of an adversarially selected sequence of clients. The ...

2023

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

Distributed Optimization with Byzantine Robustness Guarantees

Lie He

As modern machine learning continues to achieve unprecedented benchmarks, the resource demands to train these advanced models grow drastically. This has led to a paradigm shift towards distributed training. However, the presence of adversariesâ whether ma ...

EPFL2023

Updates on Hydrogen Value Chain: A Strategic Roadmap

Michael Graetzel, Dan Ren

A strategic roadmap for noncarbonized fuels is a global priority, and the reduction of carbon dioxide emissions is a key focus of the Paris Agreement to mitigate the effects of rising temperatures. In this context, hydrogen is a promising noncarbonized fue ...

WILEY-V C H VERLAG GMBH2023

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

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

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

Exact Algorithms for Continuous Pricing with Advanced Discrete Choice Demand Models

Michel Bierlaire, Fabian Alejandro Torres Duran, Tom Haering

We present the Breakpoint Exact Algorithm (BEA) together with a Spatial Branch and Bound (B&B), and Spatial Branch and Benders Decomposition (B&BD) approach to tackle the uncapacitated choice-based pricing problem (CPP) where demand is captured by a disc ...

2023

A continuum approximation approach to the depot location problem in a crowd-shipping system

Nikolaos Geroliminis, Patrick Stefan Adriaan Stokkink

Last-mile delivery in the logistics chain contributes to congestion in urban networks due to frequent stops. Crowd-shipping is a sustainable and low-cost alternative to traditional delivery but relies heavily on the availability of occasional couriers. In ...

PERGAMON-ELSEVIER SCIENCE LTD2023