Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

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

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

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

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

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

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho aro ...

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

The task of optimally designing and scheduling energy systems with a high share of renewable energies is complex and computationally demanding. A widespread method for tackling this task is to apply mixed integer linear programming (MILP). Even though the ...

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around ...

Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are int ...

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

This thesis develops mathematical programming frameworks to operate electric autonomous vehicles in the context of ride-sharing services. The introduced problem is a novel variant of the Dial-a-Ride Problem (DARP), denoted by the electric Autonomous Dial-a ...

The effective representation, processing, analysis, and visualization of large-scale structured data, especially those related to complex domains, such as networks and graphs, are one of the key questions in modern machine learning. Graph signal processing ...

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

This manuscript extends the relaxation theory from nonlinear elasticity to electromagnetism and to actions defined on paths of differential forms. The introduction of a gauge allows for a reformulation of the notion of quasiconvexity in Bandyopadhyay et al ...

Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm

Chat with Graph Search

Learning to Remove Cuts in Integer Linear Programming

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

Approximation Algorithms for Allocation and Network Design

Fairness and Explainability in Clustering Problems

Results on Sparse Integer Programming and Geometric Independent Sets

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Fair colorful k-center clustering

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

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Data reduction for mixed integer linear programming in complex energy systems

Fair Colorful k-Center Clustering

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

Local approximation of the Maximum Cut in regular graphs

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

The electric autonomous dial-a-ride problem

Graph Signal Processing for Machine Learning: A Review and New Perspectives

New Graph Algorithms via Polyhedral Techniques

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Local Approximation of the Maximum Cut in Regular Graphs

Quasiconvexity and Relaxation in Optimal Transportation of Closed Differential Forms