In this paper, we address the problem of processing reverse top-k queries in a parallel and distributed setting. Given a database of objects, a set of user preferences, and a query object q, the reverse top-k query returns the subset of user preferences for which the query object belongs to the top-k results. Although recently, the reverse top-k query operator has been studied extensively, its CPU-intensive nature results in prohibitively expensive processing cost, when applied on vast-sized data sets. This limitation motivates us to explore a parallel processing solution, to enable reverse top-k query evaluation over GBs of data in reasonable execution time. To the best of our knowledge, this is the first work that addresses the problem of parallel reverse top-k query processing. We propose a solution to this problem, called DiPaRT, which is based on MapReduce and is provably correct. DiPaRT is empirically evaluated using GB-sized data sets.

We look into the realization of mobile crowdsensing campaigns that draw on the opportunistic networking paradigm, as practised in delay-tolerant networks but also in the emerging device-to-device communication mode in cellular networks. In particular, we ask how mobile users can be optimally selected in order to generate the required space-time paths across the network for collecting data from a set of fixed locations. The users hold different roles in these paths, from collecting data with their sensing-enabled devices to relaying them across the network and uploading them to data collection points with Internet connectivity. We first consider scenarios with deterministic node mobility and formulate the selection of users as a minimum-cost set cover problem with a submodular objective function. We then generalize to more realistic settings with uncertainty about the user mobility. A methodology is devised for translating the statistics of individual user mobility to statistics of spacetime path formation and feeding them to the set cover problem formulation. We describe practical greedy heuristics for the resulting NP-hard problems and compute their approximation ratios. Our experimentation with real mobility datasets (a) illustrates the multiple tradeoffs between the campaign cost and duration, the bound on the hopcount of space-time paths, and the number of collection points; and (b) provides evidence that in realistic problem instances the heuristics perform much better than what their pessimistic worst-case bounds suggest.

We design and analyze deterministic truthful approximation mechanisms for multi-unit Combinatorial Auctions involving only a constant number of distinct goods, each in arbitrary limited supply. Prospective buyers (bidders) have preferences over multisets of items, i.e., for more than one unit per distinct good. Our objective is to determine allocations of multisets that maximize the Social Welfare. Our main results are for multi-minded and submodular bidders. In the first setting each bidder has a positive value for being allocated one multiset from a prespecified demand set of alternatives. In the second setting each bidder is associated to a submodular valuation function that defines his value for the multiset he is allocated. For multi-minded bidders, we design a truthful FPTAS that fully optimizes the Social Welfare, while violating the supply constraints on goods within factor (1+e), for any fixed e>0 (i.e., the approximation applies to the constraints and not to the Social Welfare). This result is best possible, in that full optimization is impossible without violating the supply constraints. For submodular bidders, we obtain a PTAS that approximates the optimum Social Welfare within factor (1+e), for any fixed e>0, without violating the supply constraints. This result is best possible as well. Our allocation algorithms are Maximal-in-Range and yield truthful mechanisms, when paired with Vickrey-Clarke-Groves payments.

We present and analyze a mechanism for the Combinatorial Public Project Problem (CPPP). The problem asks to select k out of m available items, so as to maximize the social welfare for autonomous agents with combinatorial preferences (valuation functions) over subsets of items. The CPPP constitutes an abstract model for decision making by autonomous agents and has been shown to present severe computational hardness, in the design of truthful approximation mechanisms. We study a non-truthful mechanism that is, however, practically relevant to multi-agent environments, by virtue of its natural simplicity. It employs an Item Bidding interface, wherein every agent issues a separate bid for the inclusion of each distinct item in the outcome; the k items with the highest sums of bids are chosen and agents are charged according to a VCG-based payment rule. For fairly expressive classes of the agents' valuation functions, we establish existence of socially optimal pure Nash and strong equilibria, that are resilient to coordinated deviations of subsets of agents. Subsequently we derive tight worst-case bounds on the approximation of the optimum social welfare achieved in equilibrium. We show that the mechanism's performance improves with the number of agents that can coordinate, and reaches half of the optimum welfare at strong equilibrium.

Abstract We consider a probabilistic model for the Steiner Tree problem. Under this model, the problem is defined in a two‐stage setting over a first‐stage complete weighted graph having its vertices associated with a probability of presence (independently each from another) in the second stage. A first‐stage feasible solution on the input graph might become infeasible in the second stage, when certain vertices of the graph fail. Therefore, a well defined modification strategy is devised for modifying the remainders of a first‐stage solution to render it second‐stage feasible. The objective is to minimize the expected weight of the second‐stage solution over the distribution of all possible second‐stage materializable subgraphs of the input graph. We recognize two complementary computational problems in this setting, one being the a priori computation of first‐stage decisions given a particular modification strategy, and the second being the cost‐efficient modification of a first‐stage feasible solution. We prove that both these problems are NP‐hard for the Steiner Tree problem under this setting. We design and analyze probabilistically an efficient modification strategy and derive tight approximation results for both aforementioned problems. We show that our techniques can be extended to the case of the more general Steiner Forest problem in the same probabilistic setting. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

A commonly employed abstraction for studying the object placement problem for the purpose of Internet content distribution is that of a distributed replication group. In this work, the initial model of the distributed replication group of Leff et al. [CHECK END OF SENTENCE] is extended to the case that individual nodes act selfishly, i.e., cater to the optimization of their individual local utilities. Our main contribution is the derivation of equilibrium object placement strategies that 1) can guarantee improved local utilities for all nodes concurrently as compared to the corresponding local utilities under greedy local object placement, 2) do not suffer from potential mistreatment problems, inherent to centralized strategies that aim at optimizing the social utility, and 3) do not require the existence of complete information at all nodes. We develop a baseline computationally efficient algorithm for obtaining the aforementioned equilibrium strategies and then extend it to improve its performance with respect to fairness. Both algorithms are realizable, in practice, through a distributed protocol that requires only a limited exchange of information.

Different successful heuristic approaches have been proposed for solving combinatorial optimization problems. Commonly, each of them is specialized to serve a different purpose or address specific difficulties. However, most combinatorial problems that model real world applications have a priori well known measurable properties. Embedded machine learning methods may aid towards the recognition and utilization of these properties for the achievement of satisfactory solutions. In this paper, we present a heuristic methodology which employs the instance-based machine learning paradigm. This methodology can be adequately configured for several types of optimization problems which are known to have certain properties. Experimental results are discussed concerning two well known problems, namely the knapsack problem and the set partitioning problem. These results show that the proposed approach is able to find significantly better solutions compared to intuitive search methods based on heuristics which are usually applied to the specific problems.