Publication

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

Related publications (28)

Certification of Bottleneck Task Assignment With Shortest Path Criteria

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

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

Baiwei Guo

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

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

GRAMM: Fast CGRA Application Mapping Based on A Heuristic for Finding Graph Minors

Mirjana Stojilovic, Guanglei Zhou

A graph H is a minor of a second graph G if G can be transformed into H by two operations: 1) deleting nodes and/or edges, or 2) contracting edges. Coarse-grained reconfigurable array (CGRA) application mapping is closely related to the graph minor problem ...

Los Alamitos2023

Quantitative Methods for Omnichannel Decision-Making

Andrey Vasilyev

Omnichannel retail has emerged as the new standard in today's commerce landscape, with retailers integrating their physical and online channels to enhance the customer shopping experience. However, such integration presents significant challenges for retai ...

EPFL2023

Extractable Witness Encryption for the Homogeneous Linear Equations Problem

Serge Vaudenay, Bénédikt Minh Dang Tran

Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption construc ...

Springer2023

Maximum Independent Set: Self-Training through Dynamic Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

2023

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Karl Aberer, Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên

Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...

ELSEVIER SCIENCE INC2023

Universal and adaptive methods for robust stochastic optimization

Ali Kavis

Within the context of contemporary machine learning problems, efficiency of optimization process depends on the properties of the model and the nature of the data available, which poses a significant problem as the complexity of either increases ad infinit ...

EPFL2023

Interactive-time Exploration, Querying, and Analysis of Large High-dimensional Datasets

Sachin Basil John

In the current era of big data, aggregation queries on high-dimensional datasets are frequently utilized to uncover hidden patterns, trends, and correlations critical for effective business decision-making. Data cubes facilitate such queries by employing p ...

EPFL2023