Online-bounded analysis

Though competitive analysis is often a very good tool for the analysis of online algorithms, sometimes it does not give any insight and sometimes it gives counter-intuitive results. Much work has gone into exploring other performance measures, in particular targeted at what seems to be the core problem with competitive analysis: The comparison of the performance of an online algorithm is made with respect to a too powerful adversary. We consider a new approach to restricting the power of the adversary, by requiring that when judging a given online algorithm, the optimal offline algorithm must perform at least as well as the online algorithm, not just on the entire final request sequence, but also on any prefix of that sequence. This is limiting the adversary’s usual advantage of being able to exploit that it knows the sequence is continuing beyond the current request. Through a collection of online problems, including machine scheduling, bin packing, dual bin packing, and seat reservation, we investigate the significance of this particular offline advantage.     

三台机并行工件排序问题的改进的下界

与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。     

A note on the k-Canadian Traveller Problem

We consider the online problem k-CTP, which is the problem to guide a vehicle from some site s to some site t on a road map given by a graph G=(V,E) in which up to k (unknown) edges are blocked by avalanches. An online algorithm learns from a blocked edge when reaching one of its endpoints. Thus, it might have to change its route to the target t up to k times. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 2k+1 and give an easy algorithm which matches this lower bound. Furthermore, we show that randomization can not improve the competitive ratio substantially, by establishing a lower bound of k+1 for the competitivity of randomized online algorithms against an oblivious adversary.     

Online linear optimization and adaptive routing

This paper studies an online linear optimization problem generalizing the multi-armed bandit problem. Motivated primarily by the task of designing adaptive routing algorithms for overlay networks, we present two randomized online algorithms for selecting a sequence of routing paths in a network with unknown edge delays varying adversarially over time. In contrast with earlier work on this problem, we assume that the only feedback after choosing such a path is the total end-to-end delay of the selected path. We present two algorithms whose regret is sublinear in the number of trials and polynomial in the size of the network. The first of these algorithms generalizes to solve any online linear optimization problem, given an oracle for optimizing linear functions over the set of strategies; our work may thus be interpreted as a general-purpose reduction from offline to online linear optimization. A key element of this algorithm is the notion of a barycentric spanner, a special type of basis for the vector space of strategies which allows any feasible strategy to be expressed as a linear combination of basis vectors using bounded coefficients.We also present a second algorithm for the online shortest path problem, which solves the problem using a chain of online decision oracles, one at each node of the graph. This has several advantages over the online linear optimization approach. First, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. Second, even in the case of an oblivious adversary, the second algorithm performs slightly better than the first, as measured by their additive regret.     

Using an adversary simulator to evaluate global EDF scheduling of sporadic task sets on multiprocessors

Schedulability analysis of real-time multiprocessor systems is usually based on sufficient but not necessary tests that produce pessimistic results. One difficulty in evaluating the effectiveness of sufficient schedulability tests has been distinguishing the cause of a task set failing the test, i.e., finding out whether the task set is in fact not schedulable or it is actually schedulable but the test itself is too pessimistic. Necessary schedulability tests help to distinguish between these two situations, since if a task set fails in the test then it is guaranteed to be unschedulable. An adversary simulator is a scheduling simulator that uses the non-determinism of the task model to generate scenarios that will stress a specific scheduling algorithm, improving the odds of a deadline miss. In this paper we describe a new adversary simulator algorithm for sporadic task sets executed on multiprocessors scheduled by Global Earliest Deadline First (G-EDF). It is shown that this new adversary simulator is more effective as a necessary test than existing approaches. We also estimate the uncertainty regarding G-EDF by applying to the same task sets a well-known sufficient schedulability test from the literature and the necessary schedulability test based on the adversary simulator.     

TCP is Competitive with Resource Augmentation

The well-known Transport Control Protocol (TCP) is a crucial component of the TCP/IP architecture on which the Internet is built, and is a de facto standard for reliable communication on the Internet. At the heart of the TCP protocol is its congestion control algorithm. While most practitioners believe that the TCP congestion control algorithm performs very well, a complete analysis of the congestion control algorithm is yet to be done. A lot of effort has, therefore, gone into the evaluation of different performance metrics like throughput and average latency under TCP. In this paper, we approach the problem from a different perspective and use the competitive analysis framework to provide some answers to the question “how good is the TCP/IP congestion control algorithm?” We describe how the TCP congestion control algorithm can be viewed as an online, distributed scheduling algorithm. We observe that existing lower bounds for non-clairvoyant scheduling algorithms imply that no online, distributed, non-clairvoyant algorithm can be competitive with an optimal offline algorithm if both algorithms were given the same resources. Therefore, in order to evaluate TCP using competitive analysis, we must limit the power of the adversary, or equivalently, allow TCP to have extra resources compared to an optimal, offline algorithm for the same problem. In this paper, we show that TCP is competitive to an optimal, offline algorithm provided the former is given more resources. Specifically, we prove first that for networks with a single bottleneck (or point of congestion), TCP is ${\mathcal{O}}(1)The well-known Transport Control Protocol (TCP) is a crucial component of the TCP/IP architecture on which the Internet is built, and is a de facto standard for reliable communication on the Internet. At the heart of the TCP protocol is its congestion control algorithm. While most practitioners believe that the TCP congestion control algorithm performs very well, a complete analysis of the congestion control algorithm is yet to be done. A lot of effort has, therefore, gone into the evaluation of different performance metrics like throughput and average latency under TCP. In this paper, we approach the problem from a different perspective and use the competitive analysis framework to provide some answers to the question “how good is the TCP/IP congestion control algorithm?” We describe how the TCP congestion control algorithm can be viewed as an online, distributed scheduling algorithm. We observe that existing lower bounds for non-clairvoyant scheduling algorithms imply that no online, distributed, non-clairvoyant algorithm can be competitive with an optimal offline algorithm if both algorithms were given the same resources. Therefore, in order to evaluate TCP using competitive analysis, we must limit the power of the adversary, or equivalently, allow TCP to have extra resources compared to an optimal, offline algorithm for the same problem. In this paper, we show that TCP is competitive to an optimal, offline algorithm provided the former is given more resources. Specifically, we prove first that for networks with a single bottleneck (or point of congestion), TCP is O(1){\mathcal{O}}(1)-competitive to an optimal centralized (global) algorithm in minimizing the user-perceived latency or flow time of the sessions, provided we allow TCP O(1){\mathcal{O}}(1) times as much bandwidth and O(1){\mathcal{O}}(1) extra time per session. Second, we show that TCP is fair by proving that the bandwidths allocated to sessions quickly converge to fair sharing of network bandwidth.     

Scheduling parallel jobs to minimize the makespan

We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen. List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.     

New lower bounds for online k-server routing problems

In a k-server routing problem k?1 servers move in a metric space in order to visit specified points or carry objects from sources to destinations. In the online version requests arrive online while the servers are traveling. Two classical objective functions are to minimize the makespan, i.e., the time when the last server has completed its tour (k-Traveling Salesman Problem or k-tsp) and to minimize the sum of completion times (k-Traveling Repairman Problem or k-trp). Both problems, the k-tsp and the k-trp have been studied from a competitive analysis point of view, where the cost of an online algorithm is compared to that of an optimal offline algorithm. However, the gap between the obtained competitive ratios and the corresponding lower bounds have mostly been quite large for k>1, in particular for randomized algorithms against an oblivious adversary.We reduce a number of gaps by providing new lower bounds for randomized algorithms. The most dramatic improvement is in the lower bound for the k-Dial-a-Ride-Problem (the k-trp when objects need to be carried) from to 3 which is currently also the best lower bound for deterministic algorithms.     

Online Search with Time-Varying Price Bounds

Online search is a basic online problem. The fact that its optimal deterministic/randomized solutions are given by simple formulas (however with difficult analysis) makes the problem attractive as a target to which other practical online problems can be transformed to find optimal solutions. However, since the upper/lower bounds of prices in available models are constant, natural online problems in which these bounds vary with time do not fit in the available models.We present two new models where the bounds of prices are not constant but vary with time in certain ways. The first model, where the upper and lower bounds of (logarithmic) prices have decay speed, arises from a problem in concurrent data structures, namely to maximize the (appropriately defined) freshness of data in concurrent objects. For this model we present an optimal deterministic algorithm with competitive ratio \(\sqrt{D}\), where D is the known duration of the game, and a nearly-optimal randomized algorithm with competitive ratio \(\frac{\ln D}{1+\ln2-\frac{2}{D}}\). We also prove that the lower bound of competitive ratios of randomized algorithms is asymptotically \(\frac{\ln D}{4}\).The second model is inspired by the fact that some applications do not utilize the decay speed of the lower bound of prices in the first model. In the second model, only the upper bound decreases arbitrarily with time and the lower bound is constant. Clearly, the lower bound of competitive ratios proved for the first model holds also against the stronger adversary in the second model. For the second model, we present an optimal randomized algorithm. Our numerical experiments on the freshness problem show that this new algorithm achieves much better/smaller competitive ratios than previous algorithms do, for instance 2.25 versus 3.77 for D=128.     

Caching for Web Searching

Abstract. We study Web Caching when the input sequence is a depth first search traversal of some tree. There are at least two good motivations for investigating tree traversal as a search technique on the WWW: First, empirical studies of people browsing and searching the WWW have shown that user access patterns commonly are nearly depth first traversals of some tree. Secondly (as we will show in this paper), the problem of visiting all the pages on some WWW site using anchor clicks (clicks on links) and back button clicks—by far the two most common user actions—reduces to the problem of how best to cache a tree traversal sequence (up to constant factors). We show that for tree traversal sequences the optimal offline strategy can be computed efficiently. In the bit model, where the access time of a page is proportional to its size, we show that the online algorithm LRU is (1 + 1/ɛ) -competitive against an adversary with unbounded cache as long as LRU has a cache of size at least (1+ ɛ) times the size of the largest item in the input sequence. In the general model, where pages have arbitrary access times and sizes, we show that in order to be constant competitive, any online algorithm needs a cache large enough to store Ω(log n) pages; here n is the number of distinct pages in the input sequence. We provide a matching upper bound by showing that the online algorithm Landlord is constant competitive against an adversary with an unbounded cache if Landlord has a cache large enough to store the Ω(log n) largest pages. This is further theoretical evidence that Landlord is the ``right' algorithm for Web Caching.     

The orthogonal CNN problem

The online CNN problem had no known competitive algorithms for a long time. Sitters, Stougie and de Paepe showed that there exists a competitive online algorithm for this problem. However, both their algorithm and analysis are quite complicated, and above all, their upper bound for the competitive ratio is 10⁵. In this paper, we examine why this problem seems so difficult. To this end we introduce a nontrivial restriction, orthogonality, against this problem and show that it decreases the competitive ratio dramatically, down to at most 9.     

Semi-online scheduling problems on a small number of machines

We consider the semi-online parallel machine scheduling problem of minimizing the makespan given a priori information: the total processing time, the largest processing time, the combination of the previous two or the optimal makespan. We propose a new algorithm that can be applied to the problem with the known total or largest processing time and prove that it has improved competitive ratios for the cases with a small number of machines. Improved lower bounds of the competitive ratio are also provided by presenting adversary lower bound examples.     

基于即时学习的非线性系统自适应PID控制

当使用先进策略整定PID控制器参数时,往往要依赖于系统所辨识的模型,而模型的精度与优化算法的计算效率直接影响到系统的控制效果.本文利用即时学习算法的本质自适应特点(建模数据在时间与空间上相邻性),来提高辨识模型的精度,并基于广义最小方差的性能指标,用等价多项式的方法,推导出PID形式的控制律,从而避免其他优化算法带来的计算量,提高了控制精度与计算效率.仿真结果验证了该方法的有效性.     

Rendezvous in networks in spite of delay faults

Two mobile agents, starting from different nodes of an unknown network, have to meet at a node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents do not know any bound on the size of the network. In each round an agent decides if it remains idle or if it wants to move to one of the adjacent nodes. Agents are subject to delay faults: if an agent incurs a fault in a given round, it remains in the current node, regardless of its decision. If it planned to move and the fault happened, the agent is aware of it. We consider three scenarios of fault distribution: random (independently in each round and for each agent with constant probability \(0<p<1\)), unbounded adversarial (the adversary can delay an agent for an arbitrary finite number of consecutive rounds) and bounded adversarial (the adversary can delay an agent for at most c consecutive rounds, where c is unknown to the agents). The quality measure of a rendezvous algorithm is its cost, which is the total number of edge traversals. For random faults, we show an algorithm with cost polynomial in the size n of the network and polylogarithmic in the larger label L, which achieves rendezvous with very high probability in arbitrary networks. By contrast, for unbounded adversarial faults we show that rendezvous is not possible, even in the class of rings. Under this scenario we give a rendezvous algorithm with cost \(O(n\ell )\), where \(\ell \) is the smaller label, working in arbitrary trees, and we show that \(\varOmega (\ell )\) is the lower bound on rendezvous cost, even for the two-node tree. For bounded adversarial faults, we give a rendezvous algorithm working for arbitrary networks, with cost polynomial in n, and logarithmic in the bound c and in the larger label L.     

基于即时学习的MIMO系统滑模预测控制方法

针对MIMO非线性系统的控制问题,采用数据驱动的控制策略,将具有本质自适应能力的即时学习算法与具有强鲁棒性的滑模预测控制相结合,设计了一种基于即时学习的滑模预测（LL-SMPC）控制方法．该方法在在线局部建模的基础上,采用滑模预测控制律求取最优控制量,具有较强的自适应和抗干扰能力,并避免TDiophantine方程的求解,有效减少了计算量．通过仿真研究,验证了算法的有效性．     

Optimal Search and One-Way Trading Online Algorithms

This paper is concerned with the time series search and one-way trading problems. In the (time series) search problem a player is searching for the maximum (or minimum) price in a sequence that unfolds sequentially, one price at a time. Once during this game the player can decide to accept the current price p in which case the game ends and the player's payoff is p . In the one-way trading problem a trader is given the task of trading dollars to yen. Each day, a new exchange rate is announced and the trader must decide how many dollars to convert to yen according to the current rate. The game ends when the trader trades his entire dollar wealth to yen and his payoff is the number of yen acquired. The search and one-way trading are intimately related. Any (deterministic or randomized) one-way trading algorithm can be viewed as a randomized search algorithm. Using the competitive ratio as a performance measure we determine the optimal competitive performance for several variants of these problems. In particular, we show that a simple threat-based strategy is optimal and we determine its competitive ratio which yields, for realistic values of the problem parameters, surprisingly low competitive ratios. We also consider and analyze a one-way trading game played against an adversary called Nature where the online player knows the probability distribution of the maximum exchange rate and that distribution has been chosen by Nature. Finally, we consider some applications for a special case of portfolio selection called two-way trading in which the trader may trade back and forth between cash and one asset. Received October 19, 1998; revised August 12, 1999.     

加密模式与密码协议的安全性

密码协议的设计和安全性分析是困难的,在密码协议中总是以所使用的密码算法是安全的为前提,但是人们却忽略了密码算法的加密模式对密码协议安全性的影响。论文针对一个改进的Needham-Schroeder协议,假设其使用了分组密码的CBC加密模式,我们通过使用一条旧信息的明密文对来修改当前会话中的信息,从而成功地欺骗用户双方,并分别与他们建立了一个会话密钥,对该协议进行了成功的攻击。结果说明密码算法的加密模式对密码协议的安全性有着巨大的影响。Schroederauthenticationprotocol125     

An Algorithmic View on OVSF Code Assignment

Orthogonal Variable Spreading Factor (OVSF) codes are used in UMTS to share the radio spectrum among several connections of possibly different bandwidth requirements. The combinatorial core of the OVSF code assignment problem is to assign some nodes of a complete binary tree of height h (the code tree) to n simultaneous connections, such that no two assigned nodes (codes) are on the same root-to-leaf path. A connection that uses a 2^-d fraction of the total bandwidth requires some code at depth d in the tree, but this code assignment is allowed to change over time. Requests for connections that would exceed the total available bandwidth are rejected. We consider the one-step code assignment problem: Given an assignment, move the minimum number of codes to serve a new request. Minn and Siu propose the so-called DCA algorithm to solve the problem optimally. In contrast, we show that DCA does not always return an optimal solution, and that the problem is NP-hard. We give an exact n^O(h)-time algorithm, and a polynomial-time greedy algorithm that achieves approximation ratio Θ(h). A more practically relevant version is the online code assignment problem, where future requests are not known in advance. Our objective is to minimize the overall number of code reassignments. We present a Θ(h)-competitive online algorithm, and show that no deterministic online algorithm can achieve a competitive ratio better than 1.5. We show that the greedy strategy (minimizing the number of reassignments in every step) is not better than Ω(h) competitive. We give a 2-resource augmented online algorithm that achieves an amortized constant number of (re-)assignments. Finally, we show that the problem is fixed-parameter tractable.     

Knowledge State Algorithms

We introduce the novel concept of knowledge states. The knowledge state approach can be used to construct competitive randomized online algorithms and study the trade-off between competitiveness and memory. Many well-known algorithms can be viewed as knowledge state algorithms. A knowledge state consists of a distribution of states for the algorithm, together with a work function which approximates the conditional obligations of the adversary. When a knowledge state algorithm receives a request, it then calculates one or more “subsequent” knowledge states, together with a probability of transition to each. The algorithm uses randomization to select one of those subsequents to be the new knowledge state. We apply this method to randomized k-paging. The optimal minimum competitiveness of any randomized online algorithm for the k-paging problem is the kth harmonic number, \(H_{k}=\sum^{k}_{i=1}\frac{1}{i}\). Existing algorithms which achieve that optimal competitiveness must keep bookmarks, i.e., memory of the names of pages not in the cache. An H _k -competitive randomized algorithm for that problem which uses O(k) bookmarks is presented, settling an open question by Borodin and El-Yaniv. In the special cases where k=2 and k=3, solutions are given using only one and two bookmarks, respectively.