Search

The switch Markov chain has been extensively studied as the most natural Markovchain Monte Carlo approach for sampling graphs with prescribed degree sequences. In this work westudy the problem of uniformly sampling graphs for which, in addition to the degree sequence, jointdegree constraints are given. These constraints specify how many edges there should be between twogiven degree classes (i.e., subsets of nodes that all have the same degree). Although the problem wasformalized over a decade ago, and despite its practical significance in generating synthetic networktopologies, small progress has been made on the random sampling of such graphs. In the case of onedegree class, the problem reduces to the sampling of regular graphs (i.e., graphs in which all nodeshave the same degree), but beyond this very little is known. We fully resolve the case of two degreeclasses, by showing that the switch Markov chain is always rapidly mixing. We do this by combininga recent embedding argument developed by the authors in combination with ideas of Bhatnagar et al.[Algorithmica, 50 (2008), pp. 418--445] introduced in the context of sampling bichromatic matchings.

The framework of budget-feasible mechanism design studies procurement auctions where the auctioneer (buyer) aims to maximize his valuation function subject to a hard budget constraint. We study the problem of designing truthful mechanisms that have good approximation guarantees and never pay the participating agents (sellers) more than the budget. We focus on the case of general (non-monotone) submodular valuation functions and derive the first truthful, budget-feasible, and O(1)-approximation mechanisms that run in polynomial time in the value query model, for both offline and online auctions. Prior to our work, the only O(1)-approximation mechanism known for non-monotone submodular objectives required an exponential number of value queries. At the heart of our approach lies a novel greedy algorithm for non-monotone submodular maximization under a knapsack constraint. Our algorithm builds two candidate solutions simultaneously (to achieve a good approximation), yet ensures that agents cannot jump from one solution to the other (to implicitly enforce truthfulness). The fact that in our mechanism the agents are not ordered according to their marginal value per cost allows us to appropriately adapt these ideas to the online setting as well. To further illustrate the applicability of our approach, we also consider the case where additional feasibility constraints are present, for example, at most k agents can be selected. We obtain O(p)-approximation mechanisms for both monotone and non-monotone submodular objectives, when the feasible solutions are independent sets of a p-system. With the exception of additive valuation functions, no mechanisms were known for this setting prior to our work. Finally, we provide lower bounds suggesting that, when one cares about nontrivial approximation guarantees in polynomial time, our results are, asymptotically, the best possible.

This special issue of Climatic Change contains a series of research articles documenting co-ordinated work carried out within a 3-year European Union project 'Prediction of Regional scenarios and Uncertainties for Defining European Climate change risks and Effects' (PRUDENCE). The main objective of the PRUDENCE project was to provide high resolution climate change scenarios for Europe at the end of the twenty-first century by means of dynamical downscaling (regional climate modelling) of global climate simulations. The first part of the issue comprises seven overarching PRUDENCE papers on: (1) the design of the model simulations and analyses of climate model performance, (2 and 3) evaluation and intercomparison of simulated climate changes, (4 and 5) specialised analyses of impacts on water resources and on other sectors including agriculture, ecosystems, energy, and transport, (6) investigation of extreme weather events and (7) implications of the results for policy. A paper summarising the related MICE (Modelling the Impact of Climate Extremes) project is also included. The second part of the issue contains 12 articles that focus in more detail on some of the themes summarised in the overarching papers. The PRUDENCE results represent the first comprehensive, continental-scale intercomparison and evaluation of high resolution climate models and their applications, bringing together climate modelling, impact research and social sciences expertise on climate change.