c5ec22711f3a4a2f4a0a8ffd92167190-Supplemental-Conference.pdf

Appendix for: Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond We extend our results for One-Sided Matching to a much broader class of graph-theoretic problems. This is the case for all the problems we are interested in, and is captured by the next definition. As already discussed in the Introduction, for One-Sided Matching, Amanatidis et al. (2021) showed a Using this, we can get the analogous result for all the aforementioned problems. Using the fact that null x null x/ 2 for x 1, we get w ( ˆ M) null 2n/ 3 k null n w (M) 1 3k w ( M). We now revisit the notion of a sufficiently representative assignment .