Online Matching with General Arrivals

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.

The central task in many interactive machine learning systems can be formalized as the sequential optimization of a black-box function. Bayesian optimization (BO) is a powerful model-based framework for \emph{adaptive} experimentation, where the primary go ...

In this thesis we investigate a number of problems related to 2-level polytopes, in particular from the point of view of the combinatorial structure and the extension complexity. 2-level polytopes were introduced as a generalization of stable set polytopes ...

Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

In this paper, we design a new iterative low-complexity algorithm for computing the Walsh-Hadamard transform (WHT) of an N dimensional signal with a K-sparse WHT. We suppose that N is a power of two and K = O(N^α), scales sub-linearly in N for some α ∈ (0, ...

A computer-implemented method for determining the Walsh-Hadamard transform of N samples of a signal, comprises electing a plurality of hashing C matrices Σ1, . . . ΣC, computing C hashes of a particular length based at least on a hashing front end and the ...

A bipartite graph G is semi-algebraic in R-d if its vertices are represented by point sets P,Q subset of R-d and its edges are defined as pairs of points (p,q) epsilon P x Q that satisfy a Boolean combination of a fixed number of polynomial equations and i ...

A fundamental problem in comparative genomics is to compute the distance between two genomes in terms of its higher level organization (given by genes or syntenic blocks). For two genomes without duplicate genes, we can easily define (and almost always eff ...

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

The generation of synthetic populations through simulation methods is an important research topic and has a key application in agent-based modeling of transport and land use. The next step in this research area is the generation of complete synthetic house ...

Online Matching with General Arrivals

Chat with Graph Search

Robust Adaptive Decision Making: Bayesian Optimization and Beyond

On some problems related to 2-level polytopes

Finding Perfect Matchings in Bipartite Hypergraphs

When Stuck, Flip a Coin : New Algorithms for Large-Scale Tasks

Extension complexity of stable set polytopes of bipartite graphs

A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain

Method for determining the walsh-hadamard transform of n samples of a signal and apparatus for performing the same

A semi-algebraic version of Zarankiewicz's problem

On Computing Breakpoint Distances for Genomes with Duplicate Genes

Independence number of generalized Petersen graphs

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution