This work studies the problem of 2-dimensional searching for the 3-sided range query of the form [a, b] x (-∞, c] in both main and external memory, by considering a variety of input distributions. A dynamic linear main memory solution is proposed, which answers 3-sided queries in O(log n + t) worst case time and scales with O (log log n) expected with high probability update time, under continuous μ-random distributions of the x and y coordinates, where n is the current number of stored points and t is the size of the query output. Our expected update bound constitutes a considerable improvement over the O(log n) update time bound achieved by the classic Priority Search Tree of McCreight [23], as well as over the Fusion Priority Search Tree of Willard [30], which requires O(log n/log log n) time for all operations. Moreover, we externalize this solution, gaining O(logB n + t/B) worst case and O(logBlogn) amortized expected with high probability I/Os for query and update operations respectively, where B is the disk block size. Then, combining the Modified Priority Search Tree [27] with the Priority Search Tree [23], we achieve a query time of O(log log n + t) expected with high probability and an update time of O(log log n) expected with high probability, under the assumption that the x-coordinates are continuously drawn from a smooth distribution and the y-coordinates are continuously drawn from a more restricted class of distributions. The total space is linear. Finally, we externalize this solution, obtaining a dynamic data structure that answers 3-sided queries in O(logB log n + t/B) I/Os expected with high probability, and it can be updated in O(logB log n) I/Os amortized expected with high probability and consumes O(n/B) space, under the same assumptions.

Let M be a single s-t network of parallel links with load dependent latency functions shared by an infinite number of selfish users. This may yield a Nash equilibrium with unbounded Coordination Ratio [12, 26]. A Leader can decrease the coordination ratio by assigning flow αr on M, and then all Followers assign selfishly the (1 - α)r remaining flow. This is a Stackelberg Scheduling Instance (M,r,α), 0 ≤ α ≤ 1. It was shown [23] that it is weakly NP-hard to compute the optimal Leader's strategy.For any such network M we efficiently compute the minimum portion βM of flow r needed by a Leader to induce M's optimum cost, as well as his optimal strategy.Unfortunately, Stackelberg routing in more general nets can be arbitrarily hard. Roughgarden presented a modification of Braess's Paradox graph, such that no strategy controlling αr flow can induce ≤ 1 α times the optimum cost. However, we show that our main result also applies to any s-t net G. We take care of the Braess's graph explicitly, as a convincing example.

In this paper we examine the problem of searching for some information item in the nodes of a fully interconnected computer network, where each node contains information relevant to some topic as well as links to other network nodes that also contain information, not necessarily related to locally kept information. These links are used to facilitate the Internet users and mobile software agents that try to locate specific pieces of information. However, the links do not necessarily point to nodes containing information of interest to the user or relevant to the aims of the mobile agent. Thus an element of uncertainty is introduced. For example, when an Internet user or some search agent lands on a particular network node, they see a set of links that point to information that is, supposedly, relevant to the current search. Therefore, we can assume that a link points to relevant information with some unknown probability $p$ that, in general, is related to the number of nodes in the network (intuitively, as the network grows, this probability tends to zero since adding more nodes to the network renders some extant links less accurate or obsolete). Consequently, since there is uncertainty as to whether the links contained in a node's Web page are correct or not, a search algorithm cannot rely on following the links systematically since it may end up spending too much time visiting nodes that contain irrelevant information. In this work, we will describe and analyze a search algorithm that is only allowed to transfer a fixed amount of memory along communication links as it visits the network nodes. The algorithm is, however, allowed to use one bit of memory at each node as an ‘already visited’ flag. In this way the algorithm has its memory distributed to the network nodes, avoiding overloading the network links as it moves from node to node searching for the information. We work on fully interconnected networks for simplicity reasons and, moreover, because according to some recent experimental evidence, such networks can be considered to be a good approximation of the current structure of the World Wide Web.