In federated learning (FL), clients update their local machine learning models using private data that is not to be shared with others. In each update period, the local models are then shared with a central server that maintains a global model that is used by all the clients. In this paper we consider the problem of scheduling and bandwidth assignment for vehicles that share a wireless communication channel during the FL. The objective is to minimize the update period duration so that global model updates can occur as quickly as possible. This is done by creating a transmission schedule and a fractional bandwidth assignment for each FL update period. The problem is modeled as a mixed-integer nonlinear program (MINLP) and since the problem is NP-complete, approximation algorithms are introduced that yield near-optimal solutions. This is done by doing a binary search on the update duration using a fractional relaxation and then by applying different dependent rounding procedures to obtain valid solutions. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solutions when compared to the results obtained by an optimum direct solver on the same inputs.

A digital twin (DT) is a software version of a physical system (PS) that interacts with other objects on its behalf. In order to do so, changes in the PS must be communicated to the DT in a timely fashion, and this updating is referred to as DT synchronization. This paper addresses the Minimum Synchronization Period (MSP) problem in vehicular networks, which seeks to place DTs on execution servers (ESs) so as to minimize the maximum synchronization period for all physical systems and their DTs (PS-DT pairs), while satisfying communication and computation requirements. A novel solution is proposed by modelling the MSP problem as a multi-commodity quickest flow evacuation problem, which treats the synchronization data and processing as flow network inputs to be evacuated in the shortest possible time. Transmission and computation components are represented as network flows with linear edge delays, which enables the use of well-known techniques to find the quickest flow solution. To ensure that each DT is placed at a single execution server, an unsplittable flow rounding procedure is used that assigns DTs to servers without significantly increasing the synchronization objective. Simulation results demonstrate the quality of the MSP solutions produced by our algorithm using the optimal fractional solution as a lower bound for the optimal integral solution.

With the current high levels of energy consumption of data centers, reducing power consumption by even a small percentage is beneficial. We propose a framework for thermal-aware workload distribution in a data center to reduce cooling power consumption. The framework includes linearization of the general optimization problem and proposing a heuristic to approximate the solution for the resulting Mixed Integer Linear Programming (MILP) problems. We first define a general nonlinear power optimization problem including several cooling parameters, heat recirculation effects, and constraints on server temperatures. We propose to study a linearized version of the problem, which is easier to analyze. As an energy saving scenario and as a proof of concept for our approach, we also consider the possibility that the red-line temperature for idle servers is higher than that for busy servers. For the resulting MILP problem, we propose a heuristic for intelligent rounding of the fractional solution. Through numerical simulations, we compare our heuristics with several existing algorithms. In addition, we evaluate the performance of the solution of the linearized system on the original system. Finally, the results show that the proposed approach can reduce the cooling power consumption by more than 10 percent compared to the case of continuous utilizations and a single red-line temperature.Note to Practitioners—We present a holistic approach for thermal-aware workload distribution for power consumption reduction in data centers. We suggest that when thermal and power consumption models can be linearized, a model-independent approach can be used for optimization purposes. The standard linear problem that results presents some technical challenges to solve, for which we present intuitive and effective solution heuristics. The heuristics are simple enough that they could be used for real-time calculations. The result is that customized models and problems can be avoided (a linear model could be directly constructed from operational data, if available), allowing for the simplification of operational control problems. Our approach is evaluated for a high-fidelity model of a real data center, where both the linearization and optimization components are validated. Finally, we show how this approach can be used to effectively solve the operational problem of workload distribution in the presence of utilization-dependent server red-line temperatures.

This paper introduces algorithms for static task class partitioning in mobile computation offloading (MCO). The objective is to partition a given set of task classes into two sets that are either executed locally by the mobile device (MD) or those classes that are permitted to contend for remote edge server (ES) execution. The goal is to find the task class partition that gives the minimum mean MD power consumption subject to task completion deadlines. The paper generates these partitions for both soft and hard task completion deadlines. Two variations of the problem are considered. The first assumes that the wireless and computational capacities are given and the second generates both capacity assignments subject to an additional resource cost budget constraint. The proposed partitioning algorithms are based on heuristic class ordering methods. The paper introduces two class ordering methods, a simpler one based on a task latency criterion, and an hierarchical version that first sorts and groups classes based on a mean power consumption criterion and then orders the task classes within each group based on a task completion time criterion. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solutions for both given and optimized network resource assignments.

Digital twins (DTs) can be used to represent the behavior of real physical systems (PSs) in their interaction with other objects. Each DT periodically communicates with its PS and uses these updates to implement features that reflect the real behavior of the PS. A given feature can be implemented using different models that create the feature with differing levels of system accuracy. In this article, we study the DT model selection problem, where the DTs of multiple PSs are hosted at an execution server (ES). The objective is to maximize the minimum feature accuracy for the requested features by making appropriate model selections subject to the synchronization and ES execution constraints. The model selection problem is first formulated as an NP-complete integer program. It is then decomposed into multiple subproblems, each consisting of a modified Knapsack problem. A polynomial-time approximation algorithm is proposed using dynamic programming to solve it efficiently, by violating its constraints by at most a given factor. A generalization of the model selection problem is then given and an approximation algorithm using relaxation and dependent rounding is proposed to solve the problem efficiently with guaranteed constraint violations. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solutions.

In mobile computation offloading (MCO), mobile devices (MDs) can choose to either execute tasks locally or have them executed on a remote edge server (ES). This paper addresses the problem of assigning the wireless communication bandwidth and the ES capacity used for the task execution, so that task completion time constraints are satisfied. The objective is to minimize the average power consumption of the mobile devices, subject to a cost budget constraint for obtaining the communication and computation resources. The paper includes contributions for both soft and hard task completion deadline constraints. The problems are first formulated as mixed integer nonlinear programs (MINLPs). Approximate solutions are then obtained by decomposing the problems into a collection of convex subproblems that can be efficiently solved. Results are presented that demonstrate the quality of the proposed solutions, which can achieve near optimum performance over a wide range of system parameters.

We study the classic weighted maximum throughput problem on unrelated machines. We give a (1-1/e-ε)-approximation algorithm for the preemptive case. To our knowledge this is the first ever approximation result for this problem. It is an immediate consequence of a polynomial-time reduction we design, that uses any ρ-approximation algorithm for the single-machine problem to obtain an approximation factor of (1-1/e)ρ -ε for the corresponding unrelated-machines problem, for any ε > 0. On a single machine we present a PTAS for the non-preemptive version of the problem for the special case of a constant number of distinct due dates or distinct release dates. By our reduction this yields an approximation factor of (1-1/e) -ε for the non-preemptive problem on unrelated machines when there is a constant number of distinct due dates or release dates on each machine.

Digital twins (DTs) are virtual implementations of real physical systems (PSs) that interact with other objects on their behalf. Each PS periodically communicates with its digital twin so that the state of the DT is always sufficiently current. Using these updates, a DT can provide features that represent the real behavior of its PS using models that yield differing levels of system accuracy. In this paper, we study the DT model selection problem in wireless networks where the DTs of multiple PSs are hosted at an edge server (ES). The accuracy obtained from a given model is a function of its required amount of PS input data, the updating frequency, and the amount of computational capacity needed at the ES. The objective is to maximize the minimum achieved accuracy among the requested features by making appropriate model selections subject to wireless channel and ES resource availability. The problem is first formulated as an NP-complete integer program. The paper then uses relaxation and dependent rounding, and introduces a polynomial time approximation algorithm to obtain good solutions. A variety of simulation results are presented that demonstrate the excellent performance of the proposed solution.

Digital twins (DTs) are virtual implementations of physical systems (PSs) and can represent the states of the PSs in realtime. In order to update the DTs with changes in their corresponding PSs, the PSs should regularly send their state information data to the DTs. Each DT must be assigned to an execution server (ES) that processes the forwarded data from its corresponding PS. The output is then made available to applications that are operating at an Internet cloud server. In this article, we consider the problem of DT placement such that the maximum data request–response delay experienced by the application over all PSs is minimized, subject to maximum data age target constraints at the DTs and the application server. The problem is first formulated as an integer quadratic program (IQP) and then transformed into a semidefinite program (SDP). The problem is NP-complete. Since exact polynomial solutions are unavailable, several practical polynomial-time approximation algorithms are introduced. The algorithms are designed to give solutions with different tradeoffs between the accommodation of the application input timing latency and the achievement of data age targets.

This paper proposes a method of joint wireless network and job service allocation for use with mobile computation offloading where task completion times have deadline constraints. In this design, mobile devices (MDs) may execute a computational task locally or offload the task through a wireless network for execution on an edge server (ES). The network owner offers to lease wireless communication channels at a given set of base stations along with edge server capacity that is used for job execution. The objective is to obtain a wireless and service capacity allocation that minimizes the total energy consumption of the mobile devices, subject to a cost budget constraint and constraints on the delay incurred by offloaded task execution. The design is first formulated as a mixed integer nonlinear programming problem. An approximate solution is then obtained by decomposing it into a collection of convex subproblems that can be efficiently solved. Results are presented that demonstrate that the proposed solution achieves near optimum performance over a wide range of system parameters.

Digital twin (DT) has attracted a lot of attention from both industry and academia since it was proposed over a decade ago. A DT can be viewed as a virtual implementation of a real physical system (PS) and used as a representation of the PS for various applications. Despite the great potential of DTs in various fields, implementing DTs to obtain the desired functionality is not always straightforward. Specifically, accurate real-time synchronization between the features at a PS and its DT is essential for the DT to represent the PS. In this case, appropriate networking support is a key component to enable future DT development and applications. Currently, the research on DTs from a networking standpoint is still at an early stage, and only limited work has been done on DT implementation in practical systems. To fill this gap, this article investigates networking-related issues for DTs. Based on the existing literature, a feature-based method is provided for describing the desired properties and quality of DTs from the networking perspective. A stage-based implementation framework is presented for creating large-scale DTs for complex PSs by considering various networking constraints. Networking-related challenging issues and open research topics are discussed at the end.

This paper considers the problem of algorithmic efficiency in mobile computation offloading with Concurrent Local Execution (CLE). Online energy optimal algorithms can be developed when CLE is used to guarantee hard task deadlines while offloading over Markovian wireless channels. Unfortunately, these algorithms often have a high computational complexity, which prohibits their use in online mobile implementations. Three algorithms are introduced to reduce this complexity: Markovian Compression (MC), Time Compression (TC) and Preemption Using Continuous Offloading (Preemption-CO). MC and TC reduce the state space of the offloading Markovian process, by using a novel notion of geometric similarity, or by running an optimal online offloading algorithm in periodic time steps. In Preemption-CO, while a task is offloaded preemptively, the offloading decision at every time-slot is based on non-preemptive calculations. Our simulations show that, by applying these methods, the running times of the algorithms can be significantly reduced without suffering unreasonable performance degradation compared with the optimal energy performance.

This paper considers mobile computation offloading where task completion times are subject to hard deadline constraints. Hard deadlines are difficult to meet in conventional computation offloading due to the stochastic nature of the wireless channels involved. Rather than using binary offload decisions, we permit concurrent remote and local job execution when it is needed to ensure task completion deadlines. The paper addresses this problem for homogeneous Markovian wireless channel models. An online energy-optimal computation offloading algorithm, OnOpt, is proposed. Its energy optimality is shown by constructing a time-dilated absorbing Markov process and applying dynamic programming. Closed form results are derived for general Markovian processes, and the Gilbert-Elliott channel model is used to show how the particular structure of the Markov chain can be exploited in computing optimal offload initiation times more efficiently. It is shown that job completion time probabilities can be computed recursively, which leads to a significant reduction in the computational complexity of OnOpt. The performance of the proposed algorithm is compared to three others, namely, Immediate Offloading, Channel Threshold, and Local Execution. Performance results show that the proposed algorithm can significantly improve mobile device energy consumption compared to the other approaches while guaranteeing hard task execution deadlines.

Multi-decision mobile computation offloading occurs when a task to be remotely executed is uploaded in separate parts. Since the upload is partitioned, separate decisions are needed to determine the best time to initiate each upload. The multi-decision problem is considered for the case where execution completion times are subject to hard deadline constraints and where task offloads occur over a Markovian wireless channel. An online energy-optimal computation offloading algorithm, Multiopt (Multi-decision online Optimum), is introduced, whose optimality is proven using Markovian stopping theory. The paper presents results using the Gilbert-Elliott channel model, where task completion time probabilities can be efficiently computed using Dynamic Programming. Although the proposed algorithm is proven to be energy optimal, its performance is also compared to four others, namely, Immediate Offloading, Channel Threshold, Local Execution, as well as optimal single-part offloading. Results show that the proposed algorithm can significantly improve mobile device energy consumption compared to the other approaches while guaranteeing hard task execution deadlines.

This paper addresses the problem of scheduling transmission requests in vehicular networks so that long-term road side unit (RSU) energy costs are minimized. We demonstrate that knowledge of vehicular routes greatly improves the energy service costs and request drop ratio of RSU transmission. At the same time, simple and fast prediction algorithms can recover a significant portion of the loss incurred by a lack of vehicle route knowledge. The proposed algorithms use recent historical traffic data and simple calculations, such as Bayesian estimates, to predict the next few routing decisions by a vehicle, in order to load balance the scheduling of its requests over the RSU network. Our simulation results show that, while the common assumption in the literature of knowing the vehicle routes is indeed crucial for achieving good performance, simple algorithms can be used in cases where vehicle routes are not known ahead of time, in order to achieve comparable costs and loss ratios.

We initiate the study of a new problem on searching and fetching in a distributed environment concerning treasure-evacuation from a unit disk. A treasure and an exit are located at unknown positions on the perimeter of a disk and at known arc distance. A team of two robots start from the center of the disk, and their goal is to fetch the treasure to the exit. At any time the robots can move anywhere they choose on the disk, independently of each other, with the same speed. A robot detects an interesting point (treasure or exit) only if it passes over the exact location of that point. We are interested in designing distributed algorithms that minimize the worst-case treasure-evacuation time, i.e. the time it takes for the treasure to be discovered and brought (fetched) to the exit by any of the robots. The communication protocol between the robots is either wireless, where information is shared at any time, or face-to-face (i.e. non-wireless), where information can be shared only if the robots meet. For both models we obtain upper bounds for fetching the treasure to the exit. Our main technical contribution pertains to the face-to-face model. More specifically, we demonstrate how robots can exchange information without meeting, effectively achieving a highly efficient treasure-evacuation protocol which is minimally affected by the lack of distant communication. Finally, we complement our positive results above by providing a lower bound in the face-to-face model.

This paper considers a set of mobile users that employ cloud-based computation offloading. In order to execute jobs in the cloud, the user uploads must occur over a base station channel that is shared by all of the uploading users. Since the job completion times are subject to hard deadline constraints, this restricts the feasible set of jobs that can be processed. The system is modelled as a competitive game in which each user is interested in minimizing its own energy consumption. The game is subject to the real-time constraints imposed by the job execution deadlines, user specific channel bit rates, and the competition over the shared communication channel. The paper shows that for a wide range of parameters, a game where each user independently sets its offloading decisions always has a pure Nash equilibrium, and a Gauss-Seidel-like method for determining this equilibrium is introduced. Results are presented that illustrate that the system always converges to a Nash equilibrium using the Gauss-Seidel method. Data is also presented that show the number of iterations required, and the quality of the solutions. We find that the solutions perform well compared to a lower bound on total energy performance.

In this paper we consider mobile users that employ computation offloading. In computational offloading, users can reduce energy consumption by executing jobs on a remote cloud server, rather than locally. In order to execute a job in the cloud, a mobile user must upload the job over a base station channel which is shared by all of the uploading users. The jobs are subject to hard deadline constraints, and since the channel quality may be different for each user, this may restrict the users ability to reduce energy usage. The system is modelled as a competitive game where each user is interested in minimizing its own energy use. The game is subject to the real-time constraints imposed by job execution deadlines, user specific channel bit rates, and the competition over the shared communication channel. The paper shows that for known classes of parameters, a game where each user independently adjusts its offload decisions always has a pure Nash equilibrium, and a Gauss-Seidel-like method for determining this equilibrium is presented. Results are then presented which illustrate that the system always converges to a Nash equilibrium using Gauss-Seidel. Data is presented which show the number of Nash equilibria that are found, the number of iterations required, and the quality of the solutions obtained. In particular, we find that the solutions perform well compared to a lower bound on total energy performance.

Smart scheduling can be used to reduce infrastructure energy costs in vehicular roadside networks [1]. In this paper we consider the scheduling problem when there are multiple roadside units (RSUs) in tandem. In this case it is often desirable to load balance the energy consumption across the roadside units so that energy provisioning costs can be reduced as much as possible. We first derive an integer linear programming bound on the min-max energy usage of the roadside units for a given input sample function. This bound is used for comparisons with two proposed on-line scheduling algorithms. The first is a low complexity First-Come-First-Assigned (FCFA) scheduler that makes greedy RSU selections followed by a minimum energy time slot assignment. The second algorithm, the Greedy Flow Graph Algorithm (GFGA), makes the same RSU selection but reassigns time slots whenever a new vehicle is assigned to the same RSU. This is done using a locally optimum integer linear program that can be efficiently solved using a minimum cost flow graph. Results from a variety of experiments show that the proposed scheduling algorithms perform well when compared to the energy lower bounds. Our results also show that near-optimal results are possible but come with increased computation times compared to our heuristic algorithms.

Smart downlink scheduling can be used to reduce infrastructure-to-vehicle energy costs in delay tolerant roadside networks. In this paper we incorporate this type of scheduling into ON/OFF roadside unit sleep activity, to further reduce infrastructure power consumption. To achieve significant power savings however, the OFF-to-ON sleep transitions may be very lengthy, and this overhead must be taken into account when performing the ON state scheduling. We first incorporate the OFF/ON sleep transitions into a lower bound on energy usage that can be computed for given input sample functions. An online scheduling algorithm referred to as the Flow Graph Sleep Scheduler (FGS) is then introduced, which makes locally optimum decisions about when to initiate new ON/OFF cycles. This is done by computing an estimate of the energy needed to fulfill known vehicle communication requirements with and without the OFF period. This calculation is efficiently done using a novel minimum flow graph formulation. Results from a variety of experiments show that the proposed scheduling algorithm performs well when compared to the energy lower bound. It is especially attractive in situations where vehicle demands and arrival rates are such that the energy costs permit frequent ON/OFF cycling.

We consider a type of game theoretic dynamics in a network model where all nodes act selfishly and will forward packets only if it is to their benefit. The model we present assumes that each node receives utility from successfully sending its own flow to its destination(s) and from receiving flow, while it pays a cost (e.g., battery energy) for its transmissions. Each node has to decide whether to relay flow as an intermediate node from other sources, as relaying incurs only costs. To induce nodes into acting as intermediaries, the model implements a reputation-based mechanism which punishes non-cooperative nodes by cutting off links to them, a decision that is made in a very local fashion. In our setting, the nodes know only the state of the network in their local neighborhood, and can only decide on the amount of the flow on their outgoing edges, unlike the previously considered models where users have full knowledge of the network and can also decide the routing of flow originating from them. Given the opportunistic nature of the nodes and their very limited knowledge of the network, our simulations show the rather surprising fact that a non-negligible amount of non-trivial flow (flow over at least two hops) is successfully transmitted.

We consider a forwarding game on directed graphs where nodes need to send certain amount of flow (packets) to specific destinations, possibly through several relay nodes. All nodes in the network act selfishly and will forward packets only if it is to their benefit. The model assumes that each node receives some utility from sending it flow to the predetermined destinations and from receiving flow. However each node has to decide whether to relay flow as an intermediate node from other sources, as relaying has an associated cost. This model assumes that there is no payment scheme. Somewhat surprisingly, this game has possibly several strategies that allow a significant amount of the flow to be routed while all nodes have a positive outcome, which suggest that in this model the nodes have indeed incentives to relay flow even if payments are not explicitly allocated. Although previous theoretical work establishes the existence of these strategies (Nash equilibrium solutions), it is not known how often networks have such solutions, and what percentage of flow is actually relayed through the network. In this work we simplify the original network model, and provide the first experimental evaluation of these equilibria for various classes of graphs. We provide clear evidence that these equilibrium solutions are indeed significant and establish how these equilibria depend on various properties of the network such as average degrees and flow demand density.

Given a sequencing of jobs on a single machine, each one with a weight, processing time, and a due date, the tardiness of a job is the time needed for its completion beyond its due date. We present an FPTAS for the basic scheduling problem of minimizing the total weighted tardiness when the number of distinct due dates is fixed. Previously, an FPTAS was known only for the case where all jobs have a common due date.

We reduce the approximation factor for the vertex cover to 2 − Θ (1/√log n ) (instead of the previous 2 − Θ ln ln n /2ln n obtained by Bar-Yehuda and Even [1985] and Monien and Speckenmeyer [1985]). The improvement of the vanishing factor comes as an application of the recent results of Arora et al. [2004] that improved the approximation factor of the sparsest cut and balanced cut problems. In particular, we use the existence of two big and well-separated sets of nodes in the solution of the semidefinite relaxation for balanced cut, proven by Arora et al. [2004]. We observe that a solution of the semidefinite relaxation for vertex cover, when strengthened with the triangle inequalities, can be transformed into a solution of a balanced cut problem, and therefore the existence of big well-separated sets in the sense of Arora et al. [2004] translates into the existence of a big independent set.

We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities k . We show that by modifying the algorithms by Garg and Könemann [1998] and Fleischer [2000], we can reduce their running time on a graph with n vertices and m edges from Õ (ε −2 ( m 2 + km )) to Õ (ε −2 m 2 ) for an implicit representation of the output, or Õ (ε −2 ( m 2 + kn for an explicit representation, where Õ ( f ) denotes a quantity that is O ( f log O (1) m ). The implicit representation consists of a set of trees rooted at sources (there can be more than one tree per source), and with sinks as their leaves, together with flow values for the flow directed from the source to the sinks in a particular tree. Given this implicit representation, the approximate value of the concurrent flow is known, but if we want the explicit flow per commodity per edge, we would have to combine all these trees together, and the cost of doing so may be prohibitive. In case we want to calculate explicitly the solution flow, we modify our schemes so that they run in time polylogarithmic in nk ( n is the number of nodes in the network). This is within a polylogarithmic factor of the trivial lower bound of time Ω( nk ) needed to explicitly write down a multicommodity flow of k commodities in a network of n nodes. Therefore our schemes are within a polylogarithmic factor of the minimum possible dependencies of the running time on the number of commodities k .

We examine how the selfish behavior of heterogeneous users in a network can be regulated through economic disincentives, i.e., through the introduction of appropriate taxation. One wants to impose taxes on the edges so that any traffic equilibrium reached by the selfish users who are conscious of both the travel latencies and the taxes will minimize the social cost, i.e., will minimize the total latency. We generalize previous results of Cole, Dodis and Roughgarden that held for a single origin-destination pair to the multicommodity setting. Our approach, which could be of independent interest, is based on the formulation of traffic equilibria as a nonlinear complementarity problem by Aashtiani and Magnanti (1981), We extend this formulation so that each of its solutions will give us a set of taxes that forces the network users to conform, at equilibrium, to a certain prescribed routing. We use the special nature of the prescribed minimum-latency flow in order to reduce the difficult nonlinear complementarity formulation to a pair of primal-dual linear programs. LP duality is then enough to derive our results.

The minimum latency problem, also known as the traveling repairman problem, is a variant of the traveling salesman problem in which the starting node of the tour is given and the goal is to minimize the sum of the arrival times at the other nodes. We present a quasi-polynomial time approximation scheme (QPTAS) for this problem when the instance is a weighted tree, when the nodes lie in $\mathbb{R}^d$ for some fixed d, and for planar graphs. We also present a polynomial time constant factor approximation algorithm for the general metric case. The currently best polynomial time approximation algorithm for general metrics, due to Goemans and Kleinberg, computes a 3.59-approximation.

Object access distribution in the Web is governed by Zipf's law, in general. This property leads to effective Web caches, which store the most popular objects and typically employ the LFU replacement policy, which achieves high, and often the highest, cache hit rates. However, Web cache design based only on Zipf's law has two main disadvantages: (i) it does not exploit the temporal and spatial locality of user accesses on a per session basis, and (ii) LFU implementation is costly and impractical in many environments, because it requires statistics on all objects accessed since the beginning of a cache's operation. We consider all parameters of locality of references in the Web (temporal, spatial and popularity) and draw an analogy with processor caches. Given cache replacement policies that address different locality characteristics, we argue that there exist replacement algorithms that combine these characteristics and achieve high performance at a low cost. We describe the Window-LFU (W-LFU), a policy that combines LFU and LRU and achieves better performance than LFU at lower cost. W-LFU exploits both Zipf's law, and temporal locality by using the accesses in a recent time-window. Simulations with actual traces indicate that W-LFU provides better results than theoretically expected.

We consider the problem of testing whether the intersection of a collection of k automata is empty. The straightforward algorithm for solving this problem runs in time /spl sigma//sup k/ where a is the size of the automata. In this work we prove that the assumption that there exists a better algorithm solving the FSA intersection emptiness problem implies that nondeterministic time is in subexponential deterministic time and also separates NL from P. Furthermore, under a (more general) non-uniform variant of the assumption mentioned above we can prove that NL/spl ne/NP.

Article Approximation schemes for minimum latency problems Share on Authors: Sanjeev Arora Princeton University Princeton UniversityView Profile , George Karakostas Princeton University Princeton UniversityView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 688–693https://doi.org/10.1145/301250.301432Online:01 May 1999Publication History 28citation405DownloadsMetricsTotal Citations28Total Downloads405Last 12 Months13Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access