k-Edge-Connectivity: Approximation and LP Relaxation

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

k-Edge-Connectivity: Approximation and LP Relaxation

Chattez avec Graph Search

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

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

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

Learning to Remove Cuts in Integer Linear Programming

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

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

The Power of Two Matrices in Spectral Algorithms for Community Recovery

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

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

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Fairness and Explainability in Clustering Problems

Efficient Online Clustering with Moving Costs

Systematic benchmarking of single-cell ATAC-sequencing protocols

Distributed Optimization with Byzantine Robustness Guarantees

Updates on Hydrogen Value Chain: A Strategic Roadmap

Results on Sparse Integer Programming and Geometric Independent Sets

Hardware-Software co-design Methodologies for Edge AI Optimization

Approximation Algorithms for Allocation and Network Design

Exact Algorithms for Continuous Pricing with Advanced Discrete Choice Demand Models

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