instruction:
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.
question:
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.
answer:
Truthful Mechanisms for Matching and Clustering in an Ordinal World

question:
Practically all programming languages allow the programmer to split a program into several modules which brings along several advantages in software development. In this paper, we are interested in the area of answer-set programming where fully declarative and nonmonotonic languages are applied. In this context, obtaining a modular structure for programs is by no means straightforward since the output of an entire program cannot in general be composed from the output of its components. To better understand the effects of disjunctive information on modularity we restrict the scope of analysis to the case of disjunctive logic programs (DLPs) subject to stable-model semantics. We define the notion of a DLP-function, where a well-defined input/output interface is provided, and establish a novel module theorem which indicates the compositionality of stable-model semantics for DLP-functions. The module theorem extends the well-known splitting-set theorem and enables the decomposition of DLP-functions given their strongly connected components based on positive dependencies induced by rules. In this setting, it is also possible to split shared disjunctive rules among components using a generalized shifting technique. The concept of modular equivalence is introduced for the mutual comparison of DLP-functions using a generalization of a translation-based verification method.
answer:
Modularity Aspects of Disjunctive Stable Models

question:
We extend previous work on efficiently training linear models by applying stochastic updates to non-zero features only, lazily bringing weights current as needed. To date, only the closed form updates for the l1, l, and the rarely used l2 norm have been described. We extend this work by showing the proper closed form updates for the popular l22 and elastic net regularized models. We show a dynamic programming algorithm to calculate the proper elastic net update with only one constant-time subproblem computation per update. Our algorithm handles both fixed and decreasing learning rates and we derive the result for both stochastic gradient descent (SGD) and forward backward splitting (FoBoS). We empirically validate the algorithm, showing that on a bag-of-words dataset with 260, 941 features and 88 nonzero features on average per example, our method trains a logistic regression classifier with elastic net regularization 612 times faster than an otherwise identical implementation with dense updates.
answer:
Efficient Elastic Net Regularization for Sparse Linear Models