In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

[Q]: We study truthful mechanisms for matching and related problems in a partial information<lb>setting, where the agents’ true utilities are hidden, and the algorithm only has access to ordi-<lb>nal preference information. Our model is motivated by the fact that in many settings, agents<lb>cannot express the numerical values of their utility for different outcomes, but are still able<lb>to rank the outcomes in their order of preference. Specifically, we study problems where the<lb>ground truth exists in the form of a weighted graph of agent utilities, but the algorithm can<lb>only elicit the agents’ private information in the form of a preference ordering for each agent<lb>induced by the underlying weights. Against this backdrop, we design truthful algorithms to<lb>approximate the true optimum solution with respect to the hidden weights. Our techniques<lb>yield universally truthful algorithms for a number of graph problems: a 1.76-approximation<lb>algorithm for Max-Weight Matching, 2-approximation algorithm for Max k-matching, a 6-<lb>approximation algorithm for Densest k-subgraph, and a 2-approximation algorithm for Max<lb>Traveling Salesman as long as the hidden weights constitute a metric. We also provide im-<lb>proved approximation algorithms for such problems when the agents are not able to lie about<lb>their preferences. Our results are the first non-trivial truthful approximation algorithms for<lb>these problems, and indicate that in many situations, we can design robust algorithms even<lb>when the agents may lie and only provide ordinal information instead of precise utilities.
[A]: Truthful Mechanisms for Matching and Clustering in an Ordinal World


[Q]: We propose a novel approach to automatically produce multiple colorized versions of a grayscale image. Our method results from the observation that the task of automated colorization is relatively easy given a low-resolution version of the color image. We first train a conditional PixelCNN to generate a low resolution color for a given grayscale image. Then, given the generated low-resolution color image and the original grayscale image as inputs, we train a second CNN to generate a high-resolution colorization of an image. We demonstrate that our approach produces more diverse and plausible colorizations than existing methods, as judged by human raters in a ”Visual Turing Test”.
[A]: PIXCOLOR: PIXEL RECURSIVE COLORIZATION


[Q]: In many embedded systems, such as imaging systems, the system has a single designated purpose, and same threads are executed repeatedly. Profiling thread behavior, allows the system to allocate each thread its resources in a way that improves overall system performance. We study an online resource allocation problem, where a resource manager simultaneously allocates resources (exploration), learns the impact on the different consumers (learning) and improves allocation towards optimal performance (exploitation). We build on the rich framework of multiarmed bandits and present online and offline algorithms. Through extensive experiments with both synthetic data and real-world cache allocation to threads we show the merits and properties of our algorithms.
[A]:
Bandits meet Computer Architecture: Designing a Smartly-allocated Cache