We consider the classical single-source shortest path problem in directed weighted graphs. Eppstein proved recently an \(\Omega(n^{3})\) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this \(\Omega(n^{3})\) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm.

We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the "standard" model, in which an algorithm is allowed to swap the requested item with previous items for free. We construct an online algorithm Full-Or-Partial-Move (FPM), whose competitive ratio is at most 3.3904, improving over the previous best known bound of 4.

Abstract It is natural to generalize the online $$k$$ k -Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family $${\mathcal {S}}\subseteq 2^{[k]}$$ S ⊆ 2 [ k ] of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ S : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ S = 2 [ k ] \ { ∅ } ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ S = { [ k ] } ). As a function of $$|{\mathcal {S}}|$$ | S | and k, the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ O ( k 2 | S | ) and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ Ω ( | S | ) . For any laminar family $${\mathcal {S}}$$ S of height h, the optimal ratios are O(hk) (deterministic) and $$O(h^2\log k)$$ O ( h 2 log k ) (randomized). The special case of laminar $${\mathcal {S}}$$ S that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $$\Theta (k)$$ Θ ( k ) . Offline All-or-One Paging is

Abstract In the spanning tree congestion problem, given a connected graph G , the objective is to compute a spanning tree T in G that minimizes its maximum edge congestion, where the congestion of an edge e of T is the number of edges in G for which the unique path in T between their endpoints traverses e . The problem is known to be $$\mathbb{N}\mathbb{P}$$ N P -hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratio o ( n ). In the decision version of this problem, denoted $${\varvec{K}-\textsf {STC}}$$ K - STC , we need to determine if G has a spanning tree with congestion at most K . It is known that $${\varvec{K}-\textsf {STC}}$$ K - STC is $$\mathbb{N}\mathbb{P}$$ N P -complete for $$K\ge 8$$ K ≥ 8 , and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand, $${\varvec{3}-\textsf {STC}}$$ 3 - STC can be solved in polynomial time, with the complexity status of this problem for $$K\in { \left\{ 4,5,6,7 \right\} }$$ K ∈ 4 , 5 , 6 , 7 remaining an open problem. We substantially improve the earlier hardness results by proving that $${\varvec{K}-\textsf {STC}}$$ K - STC is $$\mathbb{N}\mathbb{P}$$ N P -complete for $$K\ge 5$$ K ≥ 5 . This leaves only the case $$K=4$$ K = 4 open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider $${\varvec{K}-\textsf {STC}}$$ K - STC restricted to graphs of radius 2, and we

Given a weighted, ordered query set \(Q\) and a partition of \(Q\) into classes, we study the problem of computing a minimum-cost decision tree that, given any query \(q\in Q\) , uses equality tests and less-than tests to determine \(q\) 's class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify \(q\) , not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes.

We study search trees with 2-way comparisons ( 2wcst ’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons ( 3wcst ’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. In 2002, Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: λ − is the largest ratio that forces the less-than test, and λ + is the smallest ratio that admits the equal-to test. They determined that λ − = 1 4 , but for the higher threshold they only showed that λ + ∈ [ 3 7 , 4 9 ] . We give the tight bound for the higher threshold, by proving that in fact λ + = 3 7 .

Abstract Modern distributed data management systems face a new challenge: how can autonomous, mutually distrusting parties cooperate safely and effectively? Addressing this challenge brings up familiar questions from classical distributed systems: how to combine multiple steps into a single atomic action, how to recover from failures, and how to synchronize concurrent access to data. Nevertheless, each of these issues requires rethinking when participants are autonomous and potentially adversarial. We propose the notion of a cross-chain deal, a new way to structure complex distributed computations that manage assets in an adversarial setting. Deals are inspired by classical atomic transactions, but are necessarily different, in important ways, to accommodate the decentralized and untrusting nature of the exchange. We describe novel safety and liveness properties, along with two alternative protocols for implementing cross-chain deals in a system of independent blockchain ledgers. One protocol, based on synchronous communication, is fully decentralized, while the other, based on semi-synchronous communication, requires a globally shared ledger. We also prove that some degree of centralization is required in the semi-synchronous communication model.

Extreme valuation and volatility of cryptocurrencies require investors to diversify often which demands secure exchange protocols. A cross-chain swap protocol allows distrusting parties to securely exchange their assets. However, the current models and protocols assume predefined user preferences for acceptable outcomes. This paper presents a generalized model of swaps that allows each party to specify its preferences on the subsets of its incoming and outgoing assets. It shows that the existing swap protocols are not necessarily a strong Nash equilibrium in this model. It characterizes the class of swap graphs that have protocols that are safe, live and a strong Nash equilibrium, and presents such a protocol for this class. Further, it shows that deciding whether a swap is in this class is NP-hard through a reduction from 3SAT, and further is$\Sigma_{2}^{\mathsf{P}}$-complete through a reduction from$\exists\forall \mathsf{DNF}$.

It is natural to generalize the online $k$-Server problem by allowing each request to specify not only a point $p$, but also a subset $S$ of servers that may serve it. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page $p$, but also a subset $S$ of cache slots, and is satisfied by having a copy of $p$ in some slot in $S$. We call this problem Slot-Heterogenous Paging. We parameterize the problem by specifying a family $\mathcal S \subseteq 2^{[k]}$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size $k$ and family $\mathcal S$: - If all request sets are allowed ($\mathcal S=2^{[k]}\setminus\{\emptyset\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard \Paging ($\mathcal S=\{[k]\}$). - As a function of $|\mathcal S|$ and $k$, the optimal deterministic ratio is polynomial: at most $O(k^2|\mathcal S|)$ and at least $Ω(\sqrt{|\mathcal S|})$. - For any laminar family $\mathcal S$ of height $h$, the optimal ratios are $O(hk)$ (deterministic) and $O(h^2\log k)$ (randomized). - The special case of laminar $\mathcal S$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $Θ(k)$. Offline All-or-One Paging is NP-hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $\mathcal P of pages, and is satisfied by fetching any page from $\mathcal P into the cache. The optimal ratios for the latter problem (with laminar family of height $h$) are at most $hk$ (deterministic) and $h\,H_k$ (randomized).

Abstract Huang and Wong (Acta Inform 21(1):113–123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler (Optimal search trees using two-way key comparisons, PhD thesis, 1994) proposed modifying Huang and Wong’s algorithm to obtain an algorithm for a different problem: computing optimal two-way comparison search trees. We show that the dynamic program underlying Spuler’s algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.

Abstract. In the online packet scheduling problem with deadlines ([Formula: see text], for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a nonnegative weight, which represents its priority. Only one packet can be transmitted in any time slot, so if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets that are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning [Formula: see text] that has been a subject of intensive study since 2001 is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a [Formula: see text]-competitive online algorithm for [Formula: see text] (where [Formula: see text] is the golden ratio), matching the previously established lower bound.

We present a simple O(n 4 ) -time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.

In the ad-hoc radio network model, nodes communicate with their neighbors via radio signals, without knowing the topology of the underlying digraph. We study the information gathering problem, where each node has a piece of information called a rumor, and the objective is to transmit all rumors to the designated target node. For the model without any collision detection we provide an O˜(n1.5) deterministic protocol, significantly improving the trivial bound of O(n2). We also consider a model with a mild form of collision detection, where a node receives a 1-bit acknowledgment if its transmission was received by at least one out-neighbor. For this model we give an O˜(n) deterministic protocol for information gathering in acyclic graphs.

We address the problem of designing microfluidic chips for sample preparation, a crucial step in many experimental processes in chemical and biological sciences. One of the objectives of sample preparation is to dilute the sample fluid, called reactant, using another fluid called buffer, to produce desired volumes of fluid with prespecified reactant concentrations. In our model these fluids are manipulated in discrete volumes called droplets. The dilution process is represented by a mixing graph whose nodes represent 1–1 micro-mixers and edges represent channels for transporting fluids. We focus on designing such mixing graphs when the given sample (also referred to as the target ) consists of a single-droplet, and the objective is to minimize total fluid waste. Our main contribution is an efficient algorithm called \(\texttt {RPRIS}\) that guarantees a better provable worst-case bound on waste and significantly outperforms state-of-the-art algorithms in experimental comparison.

Abstract Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online algorithm based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and a strict competitive ratio at most 22.641. We also show that no deterministic algorithm can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is $$n-\omega (1)$$ n-ω(1) , where n is the number of vertices in the graph.

We study online competitive algorithms for the \emph{line chasing problem} in Euclidean spaces $\reals^d$, where the input consists of an initial point $P_0$ and a sequence of lines $X_1,X_2,...,X_m$, revealed one at a time. At each step $t$, when the line $X_t$ is revealed, the algorithm must determine a point $P_t\in X_t$. An online algorithm is called $c$-competitive if for any input sequence the path $P_0, P_1,...,P_m$ it computes has length at most $c$ times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets $X_t$ are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was $28.1$, even in the plane. We significantly improve this bound, by providing a~$3$-competitive algorithm for any dimension $d$. We also improve the lower bound on the competitive ratio, from $1.412$ to $1.5358$.

In the online packet scheduling problem with deadlines (PacketScheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketScheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a ϕ-competitive online algorithm for PacketScheduling (where ϕ ≈ 1.618 is the golden ratio), matching the previously established lower bound.

We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature; yet currently the best published upper bound is 1.828 [8], still quite far from the best lower bound of ϕ≈1.618 [11], [2], [6]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of ϕ applies even to the special case of 2-bounded instances, and a ϕ-competitive algorithm for 3-bounded instances was given in [5]. Improving that result, and addressing a question posed by Goldwasser [9], we present a ϕ-competitive algorithm for 4-bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio 12(13−1)≈1.303 and we prove a nearly tight lower bound of 14(1+17)≈1.281. In fact, our lower bound result is more general: using only 2-bounded instances, for any integer ℓ≥0 we prove a lower bound of 12(ℓ+1)(1+5+8ℓ+4ℓ2) for online algorithms with ℓ-lookahead, i.e., algorithms that at time t can see all packets arriving by time t+ℓ. Finally, for non-restricted instances we show a lower bound of 1.25 for randomized algorithms with ℓ-lookahead, for any ℓ≥0.

Web 2.0 users conveniently consume content through subscribing to content generators such as Twitter users or news agencies. However, given the number of subscriptions and the rate of the subscription streams, users suffer from the information overload problem. To address this issue, we propose a novel and flexible diversification paradigm to prune redundant posts from a collection of streams. A key novelty of our diversification model is that it holistically incorporates three important dimensions of social posts, namely content, time and author. We show how different applications, such as microblogging, news or bibliographic services, require different settings for these three dimensions. Further, each dimension poses unique performance challenges towards scaling the diversification model for many users and many high-throughput streams. We show that hash-based content distance measures and graph-based author distance measures are both effective and efficient for social posts. We propose scalable real-time stream processing algorithms leveraging efficient indexes that input a social post stream and output a diversified version of the stream, diversified across all three dimensions. Next, we show how these techniques can be extended to serve multiple users by appropriately reusing indexing and computation where possible. Through extensive experiments on real Twitter data, we show that our diversification model is effective and our solutions are scalable. We show that different algorithms perform best for different application settings.

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.

Effectively exploring data generated by microblogging services is challenging due to its high volume and production rate. To ad-dress this issue, we propose a solution that helps users effectively consume information from a microblogging stream, by filtering out redundant data. We formalize our approach as a novel optimization problem termed Multi-Query Diversification Problem (MQDP). In MQDP, the input consists of a list of microblogging posts and a set of user queries (e.g. news topics), where each query matches a subset of posts. The objective is to compute the smallest subset of posts that cover all other posts with respect to a “diversity di-mension ” that may represent time or, say, sentiment. Roughly, the solution (cover) has the property that each covered post has nearby posts in the cover that are collectively related to all queries relevant to this covered post. This is distinct from previous single-query diversity problems, as we may have two nearby posts that are related to intersecting but not nested sets of queries, in which case none covers the other. Another key difference is that we do not define diversity in terms of post similarity, since posts are too short for this approach to be meaningful; instead, we focus on finding representative posts for ordered diversity dimensions like time and sentiment, which are critical in microblogging. For example, for time as the diversity dimension, the selected posts will show how certain news events unfolded over time. We prove that MQDP is NP-hard and we propose an exact dy-namic programming algorithm that is feasible for small problem instances. We also propose two approximate algorithms with prov-able approximation bounds, and show how they can be adapted for a streaming setting. Through comprehensive experiments on real data, we show that our algorithms efficiently and effectively gener-ate diverse and representative posts. 1.

The Joint Replenishment Problem (JRP) deals with optimizing shipments of goods from a supplier to retailers through a shared warehouse. Each shipment involves transporting goods from the supplier to the warehouse, at a fixed cost C, followed by a redistribution of these goods from the warehouse to the retailers that ordered them, where transporting goods to a retailer ρ has a fixed cost cρ. In addition, we incur waiting costs for each order, possibly an arbitrary non-decreasing function of time, different for each order. The objective is to minimize the overall cost of satisfying all orders, namely the sum of all shipping and waiting costs. JRP has been well studied in Operations Research and, more recently, in the area of approximation algorithms. For arbitrary waiting cost functions, the best known approximation ratio is 1.8. This ratio can be reduced to ≈ 1.574 for the JRP-D model, where there is no cost for waiting but orders have deadlines. As for hardness results, it is known that the problem is ℙ -hard and that the natural linear program for JRP has integrality gap at least 1.245. Both results hold even for JRP-D. In the online scenario, the best lower and upper bounds on the competitive ratio are 2.64 and 3, respectively. The lower bound of 2.64 applies even to the restricted version of JRP, denoted JRP-L, where the waiting cost function is linear. We provide several new approximation results for JRP. In the offline case, we give an algorithm with ratio ≈ 1.791, breaking the barrier of 1.8. We also show that the integrality gap of the linear program for JRP-L is at least 12/11 ≈ 1.09. In the online case, we show a lower bound of ≈ 2.754 on the competitive ratio for JRP-L (and thus JRP as well), improving the previous bound of 2.64. We also study the online version of JRP-D, for which we prove that the optimal competitive ratio is 2.

BACKGROUND: PRISE2 is a new software tool for designing sequence-selective PCR primers and probes. To achieve high level of selectivity, PRISE2 allows the user to specify a collection of target sequences that the primers are supposed to amplify, as well as non-target sequences that should not be amplified. The program emphasizes primer selectivity on the 3' end, which is crucial for selective amplification of conserved sequences such as rRNA genes. In PRISE2, users can specify desired properties of primers, including length, GC content, and others. They can interactively manipulate the list of candidate primers, to choose primer pairs that are best suited for their needs. A similar process is used to add probes to selected primer pairs. More advanced features include, for example, the capability to define a custom mismatch penalty function. PRISE2 is equipped with a graphical, user-friendly interface, and it runs on Windows, Macintosh or Linux machines. RESULTS: PRISE2 has been tested on two very similar strains of the fungus Dactylella oviparasitica, and it was able to create highly selective primers and probes for each of them, demonstrating the ability to create useful sequence-selective assays. CONCLUSIONS: PRISE2 is a user-friendly, interactive software package that can be used to design high-quality selective primers for PCR experiments. In addition to choosing primers, users have an option to add a probe to any selected primer pair, enabling design of Taqman and other primer-probe based assays. PRISE2 can also be used to design probes for FISH and other hybridization-based assays.

We consider online competitive algorithms for the problem of collecting weighted items from a dynamic queue S . The content of S varies over time. An update to S can occur between any two consecutive time steps, and it consists in deleting any number of items at the front of S and inserting other items into arbitrary locations in S . At each time step we are allowed to collect one item in S . The objective is to maximize the total weight of collected items. This is a generalization of bounded-delay packet scheduling (also known as buffer management). We present several upper and lower bounds on the competitive ratio for the general case and for some restricted variants of this problem.

Discrete tomography deals with reconstructing finite spatial objects from their projections. The objects we study in this paper are called tilings or tile-packings, and they consist of a number of disjoint copies of a fixed tile, where a tile is defined as a connected set of grid points. A row projection specifies how many grid points are covered by tiles in a given row; column projections are defined analogously. For a fixed tile, is it possible to reconstruct its tilings from their projections in polynomial time? It is known that the answer to this question is affirmative if the tile is a bar (its width or height is 1), while for some other types of tiles $\mathbb {NP}$ -hardness results have been shown in the literature. In this paper we present a complete solution to this question by showing that the problem remains $\mathbb {NP}$ -hard for all tiles other than bars.

We prove strong ${\mathbb {NP}}$ -completeness for the four variants of caching with multi-size pages. These four variants are obtained by choosing either the fault cost or the bit cost model, and by combining it with either a forced or an optional caching policy. This resolves two questions in the area of paging and caching that were open since the 1990s.

The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining a satisfactory level of performance. One common method for saving energy is to simply suspend the system during idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the article, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses one unit of energy per one unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O ( n 5 )-time algorithm. In addition we provide an O ( n 4 )-time algorithm for computing the minimum energy schedule when all jobs have unit length.

What topologies should be used to evaluate protocols for interdomain routing? Using the most current Internet topology is not practical since its size is prohibitive for detailed, packet-level interdomain simulations. Besides being of moderate size, the topology should be policy-aware, that is, it needs to represent business relationships between adjacent nodes (that represent autonomous systems). In this paper, we address this issue by providing a framework to generate small, realistic, and policy-aware topologies. We propose HBR, a novel sampling method, which exploits the inherent hierarchy of the policy-aware Internet topology. We formally prove that our approach generates connected and legitimate topologies, which are compatible with the policy-based routing conventions and rules. Using simulations, we show that HBR generates topologies that: 1) maintain the graph properties of the real topology; 2) provide reasonably realistic interdomain simulation results while reducing the computational complexity by several orders of magnitude as compared to the initial topology. Our approach provides a permanent solution to the problem of interdomain routing evaluations: Given a more accurate and complete topology, HBR can generate better small topologies in the future.

High on-chip temperature impairs the processor's reliability and reduces its lifetime. Hardware-level dynamic thermal management (DTM) techniques can effectively constrain the chip temperature, but degrades the performance. We propose an OS-level technique that performs thermal-aware job scheduling to reduce DTMs. The algorithm is based on the observation that hot and cool jobs executed in a different order can make a difference in resulting temperature. Real-system implementation in Linux shows that our scheduler can remove 10.5% to 73.6% of the hardware DTMs in a medium thermal environment. The CPU throughput is improved by up to 7.6% (4.1%, on average) in a severe thermal environment.

We consider the problem of collecting weighted items from a dynamic queue . Before each step, some items at the front of can be deleted and some other items can be added to at any place. An item, once deleted, cannot be re-inserted — in other words, it “expires”. We are allowed to collect one item from per step. Each item can be collected only once. The objective is to maximize the total weight of the collected items. We study the online version of the dynamic queue problem. It is quite easy to see that the greedy algorithm that always collects the maximum-value item is 2-competitive, and that no deterministic online algorithm can be better than 1.618-competitive. We improve both bounds: We give a 1.89-competitive algorithm for general dynamic queues and we show a lower bound of 1.632 on the competitive ratio. We also provide other upper and lower bounds for restricted versions of this problem. The dynamic queue problem is a generalization of the well-studied buffer management problem, and it is an abstraction of the buffer management problem for network links with intermittent access.

The Internet community has not reached a consensus on an appropriate topological model for evaluating the performance of inter-domain routing protocols. Using the current Internet topology is not realistic, since its size is prohibitively large for, say, a packet-level BGP simulation. Furthermore, routing policies, which play a critical role in inter-domain routing, are often ignored in many simulation studies. In this paper, we address this issue by designing an algorithm to generate small-scale, realistic, and policy-aware topologies. We propose HBR, a network sampling method, which produces topologies that preserve the fundamental properties of the Internet graph, including, in particular, its hierarchical structure. Our approach provides a long-term solution to the difficult problem of AS-level routing evaluations: it can be used to generate small realistic topologies in the future, starting from any newer or more complete Internet instance.

The evolution of microprocessors has been hindered by their increasing power consumption and the heat generation speed on-die. High temperature impairs the processor's reliability and reduces its lifetime. While hardware level dynamic thermal management (DTM) techniques, such as voltage and frequency scaling, can effectively lower the chip temperature when it surpasses the thermal threshold, they inevitably come at the cost of performance degradation. We propose an OS level technique that performs thermal- aware job scheduling to reduce the number of thermal trespasses. Our scheduler reduces the amount of hardware DTMs and achieves higher performance while keeping the temperature low. Our methods leverage the natural discrepancies in thermal behavior among different workloads, and schedule them to keep the chip temperature below a given budget. We develop a heuristic algorithm based on the observation that there is a difference in the resulting temperature when a hot and a cool job are executed in a different order. To evaluate our scheduling algorithms, we developed a lightweight runtime temperature monitor to enable informed scheduling decisions. We have implemented our scheduling algorithm and the entire temperature monitoring framework in the Linux kernel. Our proposed scheduler can remove 10.5-73.6% of the hardware DTMs in various combinations of workloads in a medium thermal environment. As a result, the CPU throughput was improved by up to 7.6% (4.1% on average) even under a severe thermal environment.

In queue-based scheduling systems jobs are executed according to a predefined sequential plan. During exe- cution, faults may occur that cause jobs to re-execute, thus delaying the whole schedule. It is thus important to determine (in real-time) whether the given set of pre- ordered jobs is fault-tolerant, that is, if all jobs will al- ways meet their deadlines. This allows, for instance, to decide online whether to admit a new urgent job into the queue while still guaranteeing that the whole sched- ule remains fault-tolerant. Our goal in this work is to design efficient algorithm for testing fault tolerance of sequenced jobs in the presence of transient faults. We consider different fault models that specify which fault patterns are allowed to occur and how soon failed jobs can be restarted. For each fault model we provide ef- ficient algorithms that determine the feasibility of all jobs in the schedule. Our algorithms are exact and run in time linear in the number of jobs (deterministically, or with very high probability, depending on the fault model), and thus can be used to make real-time deci- sions.

We study the problem of waking up a collection of n processors connected by a multihop ad hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. Each node in the network either wakes up spontaneously or gets activated by receiving a wake‐up signal from another node. All active nodes transmit the wake‐up signals according to a given protocol $\calW$. The running time of $\calW$ is the number of steps counted from the first spontaneous wake‐up until all nodes become activated. We provide two protocols for this problem. The first one is a deterministic protocol with running time $O(n^{5/3}\log n)$. Our protocol is based on a novel concept of a shift‐tolerant selector to which we refer as a (radio) synchronizer. The second protocol is randomized, and its expected running time is $O(D \log^2 n)$, where D is the diameter of the network. Subsequently we show how to employ our wake‐up protocols to solve two other communication primitives: leader election and clock synchronization.

We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single‐processor nonpreemptive schedule that maximizes the number of completed jobs. In the online version, each job arrives at its release time. We give two online algorithms with competitive ratios below 2 and show several lower bounds on the competitive ratios. First, we give a barely random $5/3$‐competitive algorithm that uses only one random bit. We also show a lower bound of $3/2$ on the competitive ratio of barely random algorithms that randomly choose one of two deterministic algorithms. If the two algorithms are selected with equal probability, we can further improve the bound to $8/5$. Second, we give a deterministic $3/2$‐competitive algorithm in the model that allows restarts, and we show that in this model the ratio $3/2$ is optimal. For randomized algorithms with restarts we show a lower bound of $6/5$.

We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the article is an online 64/33 ≈ 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. For the 2-uniform case we give an algorithm with ratio ≈ 1.377 and a matching lower bound.

The address sequence on the processor-memory bus can reveal abundant information about the control flow of a program. This can lead to critical information leakage such as encryption keys or proprietary algorithms. Addresses can be observed by attaching a hardware device on the bus that passively monitors the bus transaction. Such side-channel attacks should be given rising attention especially in a distributed computing environment, where remote servers running sensitive programs are not within the physical control of the client.Two previously proposed hardware techniques tackled this problem through randomizing address patterns on the bus. One proposal permutes a set of contiguous memory blocks under certain conditions, while the other approach randomly swaps two blocks when necessary. In this paper, we present an anatomy of these attempts and show that they impose great pressure on both the memory and the disk. This leaves them less scalable in high-performance systems where the bandwidth of the bus and memory are critical resources. We propose a lightweight solution to alleviating the pressure without compromising the security strength. The results show that our technique can reduce the memory traffic by a factor of 10 compared with the prior scheme, while keeping almost the same page fault rate as a baseline system with no security protection.

In the Minimum Common String Partition problem (MCSP), we are given two strings on input, and we wish to partition them into the same collection of substrings, minimizing the number of the substrings in the partition. This problem is NP-hard, even for a special case, denoted 2-MCSP, where each letter occurs at most twice in each input string. We study a greedy algorithm for MCSP that at each step extracts a longest common substring from the given strings. We show that the approximation ratio of this algorithm is between Ω( n 0.43 ) and O ( n 0.69 ). In the case of 2-MCSP, we show that the approximation ratio is equal to 3. For 4-MCSP, we give a lower bound of Ω(log n ).

Abstract We present an O ( n log 4 n )‐time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O ( n 3/2 log 2 n ). © 2004 Wiley Periodicals, Inc.

We establish an O(n log/sup 2/n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of /spl Omega/(n log n). The fastest previously known algorithm for this problem works in time O(n/sup 3/2/). Using our broadcasting algorithm, we develop an O(n/sup 3/2/log/sup 2/n) algorithm for gossiping in the same network model.

In this paper, we investigate the area and volume requirement of convex drawings of planar graphs in two and three dimensions, under various resolution rules. Let G be a triconnected planar graph with n vertices. We provide O(n)-time algorithms for constructing the following types of drawings of G: ffl a 2D convex grid drawing of G with (3n) \\Theta (3n=2) area under the edge resolution rule (in the L 1 metric). ffl a 2D strictly convex grid drawing of G with O(n 3 ) \\Theta O(n 3 ) area under the edge resolution rule (in the L 1 metric). ffl a 2D strictly convex drawing of G with O(1) \\Theta O(n) area under the vertex-resolution rule, and with vertex coordinates represented by O(n log n)-bit rational numbers; ffl a 3D convex drawing of G with O(1)\\ThetaO(1)\\ThetaO(n) volume under the vertex-resolution rule, and with vertex coordinates represented by O(n log n)-bit rational numbers. We also show the following lower bounds on the area/volume of 2D/3D convex drawings under the edg...

The k-server problem is investigated when the metric space is a tree. For this case an on-line k-competitive algorithm for k-servers is presented. The competitiveness ratio k is optimal. The algorithm is memoryless, in the sense that it does not use any information from the past.

In the k-server problem, one must choose how k mobile servers will serve each of a sequence of requests, making decisions in an online manner. An optimal deterministic online strategy is exhibited when the requests fall on the real line. For the weighted-cache problem, in which the cost of moving to x from any other point is $w( x )$, the weight of x, an optimal deterministic algorithm is also provided. The nonexistence of competitive algorithms for the asymmetric two-server problem and of memoryless algorithms for the weighted-cache problem is proved. A fast algorithm for oflline computing of an optimal schedule is given, and it is shown that finding an optimal offline schedule is at least as hard as the assignment problem.

A new method for dealing with the server problem is proposed. The technique consists of embedding the given metric space M into a bigger metric space $\text{cl} ( M )$ called the closure of M, and allowing our servers to move in $\text{cl} ( M )$. How this technique can be applied to give a new optimal algorithm for two servers is shown.

Let. o~(G) denote the independence numbe>~f a graph G, that is the ma.xinmrn number of pairwise independent vertices in G.We present a parallel algorithm that computes in a planar graph G-= (V, E), an independent set I C V such that III >_ a(G)/2.The algorithm runs in time O(log 2 n) and requires a linear number of processors.This is achieved by defining a set. of reductions that can be executed "locally" and simultaneously; fllrtherrnore, it is shown that a constant fraction of the vertices in the graph are reducible.This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.

We show that a 5-colouring of the vertices of an n-vertex planar graph may be computed in $O(\log n\log ^ * n)$ time by an exclusive-read exclusive-write parallel RAM with $O({n / {(\log n\log ^ * n)}})$ processors. Our algorithm, while faster than all previously known methods, is at the same time the first parallel 5-colouring algorithm to exhibit an optimal speedup. Optimality is achieved through a method based on the accelerating cascades technique and of independent interest. It should be emphasized that although input to the algorithm is a planar graph, we do not require a planar embedding to be given as part of the input. Other results concern the colouring of graphs of bounded genus and the construction of search structures for triangular planar subdivisions.

We resolve the following long-standing conjecture of Harrison and Ibarra in 1968 [HI, p.462]: There are languages accepted by (k+1)-head 1-way deterministic pushdown automata ((k+1)-DPDA) but not by k-head 1-way pushdown automata (k-PDA), for every k. (Partial solutions for this conjecture can be found in [M1,M2,C].) On the assumption that their conjecture holds, [HI] also derived many important consequences. Now all those consequences become theorems. For example, the class of languages accepted by k-PDA's is not closed under ∩ and complementation. Several other interesting consequences also follow: CFL ⊆∪kDPDA(k) and FA(2)⊆∪kDPDA(k), where DPDA (k)={L|L is accepted by a k-DPDA} and FA(2)={L|L is accepted by a 2-head FA). Our new proof itself is also interesting in the sense that the k+l versus k heads problems was solved by diagonalization methods [I2,M2,M3,M4,S] for stronger machines (2-way, etc). and by traditional counting arguments [S2,IK,YR,M1] for weaker machines (k-FA, k-head counter machine, etc).