Title: Multicut
| Speakers: | Tom Iagovet & Hadas Barabash |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: The Multicut problem asks to separate certain pairs of vertices in a graph. The problem is $\mathbf{NP}$-hard, even on trees of height one. In this talk, we give an overview of existing results and provide insights into new approximation algorithms from this summer.
Title: Sequential Contracts on Matroids
| Speaker: | Yun Xing |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: We start with considering the max weighted independent set problem on matroids with a stochastic weight assigned to each element. To probe the exact weight of elements, one needs to pay a price. The principal asks the agent to give an independent set that is fully probed. The agent needs to pay the probe prices at his own costs, and the principal will set up a contract to compensate the agent according to the total weight of the independent set returned by the agent. Assume the agent is always maximizing his revenue, we ask the following question: can we compute/approximate the optimal contract for the principal efficiently? In this talk, we give hardness results for the general question and provide positive results for certain types of contracts/matroids.