Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

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.

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

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

Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, ...

Reaction optimization is challenging and traditionally delegated to domain experts who iteratively pro-pose increasingly optimal experiments. Problematically, the reaction landscape is complex and often requires hundreds of experiments to reach convergence ...

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

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

Gas bearings use pressurized gas as a lubricant to support and guide rotating machinery. These bearings have a number of advantages over traditional lubricated bearings, including higher efficiency in a variety of applications and reduced maintenance requi ...

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

Time-sensitive networks, as in the context of IEEE Time-Sensitive Networking (TSN) and IETF Deterministic Networking (DetNet), offer deterministic services with guaranteed bounded latency in order to support safety-critical applications. In this thesis, we ...

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

We address for the first time the problem of correcting group discriminations within a score function, while minimizing the individual error. Each group is described by a probability density function on the set of profiles. We first solve the problem analy ...

The decentralisation and unpredictability of new renewable energy sources require rethinking our energy system. Data-driven approaches, such as reinforcement learning (RL), have emerged as new control strategies for operating these systems, but they have n ...

Future low-carbon societies will need to store vast amounts of electricity to stabilize electricity grids and to power electric vehicles. Vehicle-to-grid allows vehicle owners and grid operators to share the costs of electricity storage by making the batte ...

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

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

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

Hydropower plants play a crucial role in the power system facing ambitious renewable energy targets. Due to their inherent controllability, they are well suited to provide flexibility to the grid. However, an increased flexibility provision leads to a prol ...

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Chat with Graph Search

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

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

Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

Bayesian Optimization for Chemical Reactions

Discrete Optimal Transport with Independent Marginals is #P-Hard

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Parametric Reduced Order Model of a Gas Bearings Supported Rotor

Streaming and Matching Problems with Submodular Functions

Worst-Case Delay Analysis of Time-Sensitive Networks with Network Calculus

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Removing Algorithmic Discrimination (With Minimal Individual Error)

Reinforcement Learning for Joint Design and Control of Battery-PV Systems

Vehicle-to-Grid for Reliable Frequency Regulation

Quantitative Methods for Omnichannel Decision-Making

Universal and adaptive methods for robust stochastic optimization

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Structural impact of the start-up sequence on Pelton turbines lifetime: Analytical prediction and polynomial optimization

The double exponential runtime is tight for 2-stage stochastic ILPs