Recursive local amoeba construction.

Event Date: Sep 28, 2022 in ACGO, Seminars

Abstract: Amoeba graphs were born as examples of balanceable graphs, which are graphs that appear in any 2-edge coloring of the edges of a large enough $K_n$ with a sufficient amount of red and blue edges. As they were studied further, interesting aspects were found. An edge replacement $e\to e$ in a labeled graph G means to take an edge e in E(G) and replace it with e’ \in E(\overline{G})\cup \{e\}$. If $G-e+e’$ is isomorphic to $G$ then we say $e\to e’$ is a \emph{feasible edge replacement}. Every edge replacement yields a set of permutations of the labels in $G$. The set...

Read More

Bayesian Persuasion With Costly Information Acquisition.

Event Date: Sep 21, 2022 in ACGO, Seminars

Abstract: We consider a Bayesian persuasion model in which the receiver can gather independent information about the state at a uniformly posterior-separable cost. We show that the sender provides information that prevents the receiver from gathering independent information in equilibrium. When the receiver faces a lower cost of information, her `threat’ of gathering independent information increases, thus decreasing the sender’s power to persuade. A lower cost of information can also hurt the receiver because the sender may provide strictly less information in equilibrium....

Read More

The kidney exchange problem: length-constrained cycles and chains optimization on compatibility graphs.

Event Date: Sep 07, 2022 in ACGO, Seminars

Abstract: The kidney exchange problem is a combinatorial optimization problem that arises naturally when implementing centralized kidney exchange programs. Given a directed weighted graph (called the compatibility graph), we aim to find a collection of simple and vertex-disjoint cycles maximizing the total weight of their participating arcs. Because of logistical considerations, a bound k is placed on the length of each possible cycle. We will briefly explain how the problem is polynomially solvable in the cases k = 2 and unbounded k, and why it turns NP-complete for k >= 3. MIP...

Read More

Solidarity Cover Problem.

Event Date: Aug 24, 2022 in ACGO, Seminars

Abstract: This work started with a real-world problem where the task was to partition a set of locations into disjoint subsets such that each subset is spread in a way that it covers the whole set with a certain radius. This made us formalizing the following problem which we call Solidarty Cover Problem. Given a finite set S, a metric d, and a radius r, and a number of partitions m. We define a subset C of S to be an r-cover if B(C,r)=S. The Solidarity Cover Problem is the problem of determining whether there exist m disjoint r-covers. We consider the optimization problems of maximizing the...

Read More

Prophet Inequalities via the Expected Competitive Ratio.

Event Date: Aug 17, 2022 in ACGO, Seminars

Abstract: We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements and needs to decide immediately and irrevocably whether or not to select each element upon its arrival, subject to an underlying feasibility constraint. Traditionally, the decision-maker’s expected performance has been compared to the expected performance of the prophet, i.e., the expected offline optimum. We refer to this measure as the Ratio of Expectations (or, in short, RoE). However, a major limitation of the RoE measure...

Read More

Machine Covering in the Random-Order Model.

Event Date: Jul 27, 2022 in ACGO, Seminars

Abstract: In the Online Machine Covering problem, jobs, defined by their sizes, arrive one by one and have to be assigned to m parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. Unfortunately, the classical model allows only fairly pessimistic performance guarantees: The best possible deterministic ratio of m is achieved by the Greedy-strategy, and the best known randomized algorithm has competitive ratio Õ(m^(1/2)), which cannot be improved by more than a logarithmic factor. In this talk, we will discuss results for the Machine Covering...

Read More