Fair Colorful k-Center Clustering

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.

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

Clustering in education, particularly in large-scale online environments like MOOCs, is essential for understanding and adapting to diverse student needs. However, the effectiveness of clustering depends on its interpretability, which becomes challenging w ...

Urban proximity planning is foreseen as a solution to foster a “sustainable” city, including economic viability, environmental soundness and social inclusivity. This paper focuses on the inclusivity aspects by questioning the adoption of urban proximities: ...

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

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

Much attention has been paid to dynamical simulation and quantum machine learning (QML) independently as applications for quantum advantage, while the possibility of using QML to enhance dynamical simulations has not been thoroughly investigated. Here we d ...

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

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

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

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

Unsupervised graph representation learning aims to learn low-dimensional node embeddings without supervision while preserving graph topological structures and node attributive features. Previous Graph Neural Networks (GNN) require a large number of labeled ...

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

Knowledge of a program's input format is essential for effective input generation in fuzzing. Automated input format reverse engineering represents an attractive but challenging approach to learning the format. In this paper, we address several challenges ...

Control systems operating in real-world environments often face disturbances arising from measurement noise and model mismatch. These factors can significantly impact the perfor- mance and safety of the system. In this thesis, we aim to leverage data to de ...

The local physical properties - such as shape and flexibility - of the DNA double-helix is today widely believed to be influenced by nucleic acid sequence in a non-trivial way. Furthermore, there is strong evidence that these properties play a role in many ...

BACKGROUND:The indication for mechanical thrombectomy (MT) in stroke patients with large vessel occlusion has been constantly expanded over the past years. Despite remarkable treatment effects at the group level in clinical trials, many patients remain sev ...

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

We present Deep MinCut (DMC), an unsupervised approach to learn node embeddings for graph -structured data. It derives node representations based on their membership in communities. As such, the embeddings directly provide insights into the graph structure ...

In this paper, the recommended implementation of the post-quantum key exchange SIKE for Cortex-M4 is attacked through power analysis with a single trace by clustering with the k-means algorithm the power samples of all the invocations of the elliptic curve ...

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

Fair Colorful k-Center Clustering

Chat with Graph Search

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

Interpret3C: Interpretable Student Clustering Through Individualized Feature Selection

Planning urban proximities: An empirical analysis of how residential preferences conflict with the urban morphologies and residential practices

Learning to Remove Cuts in Integer Linear Programming

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

Dynamical simulation via quantum machine learning with provable generalization

Fairness and Explainability in Clustering Problems

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Approximation Algorithms for Allocation and Network Design

Results on Sparse Integer Programming and Geometric Independent Sets

Unsupervised Graph Representation Learning with Cluster-aware Self-training and Refining

Better Trees for Santa Claus

AIFORE: Smart Fuzzing Based on Automatic Input Format Reverse Engineering

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

Landscapes of DNA Mechanics and Genomes

Preserved Corticospinal Tract Revealed by Acute Perfusion Imaging Relates to Better Outcome After Thrombectomy in Stroke

Streaming and Matching Problems with Submodular Functions

Deep MinCut: Learning Node Embeddings by Detecting Communities

Single-Trace Clustering Power Analysis of the Point-Swapping Procedure in the Three Point Ladder of Cortex-M4 SIKE

Discrete Optimal Transport with Independent Marginals is #P-Hard