Extended Formulations from Communication Protocols in Output-Efficient Time

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.

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do n ...

With the 2010/31/EU directive, all new buildings shall be nearly zero-energy buildings (nZEB) from 2020 onward, with the aim of strongly reducing the energy consumption related to the building sector. To achieve this goal, it is not sufficient to focus on ...

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...

An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...

Materials Cloud is a platform designed to enable open and seamless sharing of resources for computational science, driven by applications in materials modelling. It hosts (1) archival and dissemination services for raw and curated data, together with their ...

Extended Formulations from Communication Protocols in Output-Efficient Time

Chat with Graph Search

Knapsack and Subset Sum with Small Items

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Efficient Streaming Subgraph Isomorphism with Graph Neural Networks

Innovative Renewable Technology Integration for Nearly Zero-Energy Buildings within the Re-COGNITION Project

New Results in Integer and Lattice Programming

Improved Ramsey-type results for comparability graphs

Simple Realizability of Complete Abstract Topological Graphs Simplified

Materials Cloud, a platform for open computational science