**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Online Matching in Evolving Environments

Description

This lecture covers the topic of online matching in evolving environments, focusing on the challenges and solutions for adapting algorithms to changing data over time. The instructor discusses the use of randomization, dynamic matching, and the concept of instance optimality. Various algorithms and techniques are explored, including the application of negative association theory and the development of adaptive online algorithms. The presentation also delves into the implications of adaptive data on algorithm design and the quest for instance-optimal solutions.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (115)

Edge coloring

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors.

Matching (graph theory)

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem. Given a graph G = (V, E), a matching M in G is a set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share common vertices.

Greedy coloring

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible. Different choices of the sequence of vertices will typically produce different colorings of the given graph, so much of the study of greedy colorings has concerned how to find a good ordering.

Randomization

Randomization is the process of making something random. Randomization is not haphazard; instead, a random process is a sequence of random variables describing a process whose outcomes do not follow a deterministic pattern, but follow an evolution described by probability distributions. For example, a random sample of individuals from a population refers to a sample where every individual has a known probability of being sampled. This would be contrasted with nonprobability sampling where arbitrary individuals are selected.

Algorithmic information theory

Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" (except for a constant that only depends on the chosen universal programming language) the relations or inequalities found in information theory.

Related lectures (70)

Variational Inference and Neural NetworksMGT-448: Statistical inference and machine learning

Covers variational inference and neural networks for classification tasks.

Unweighted Bipartite MatchingCS-450: Algorithms II

Introduces unweighted bipartite matching and its solution using linear programming and the simplex method.

Frequency Domain Study: Acoustic Response AnalysisEE-548: Audio engineering

Explores the Frequency Domain study in COMSOL for analyzing acoustic responses to harmonic excitation in various fields.

Graphical Models: Joint Probability DistributionPHYS-512: Statistical physics of computation

Covers the concept of graphical models and joint probability distributions.

Information Theory: BasicsPHYS-512: Statistical physics of computation

Covers the basics of information theory, entropy, and fixed points in graph colorings and the Ising model.