The Power of Priority Algorithms for Facility Location and Set Cover

We apply and extend the priority algorithm framework introduced by Borodin, Nielsen, and Rackoff to define greedy-like algorithms for the (uncapacitated) facility location problems and set cover problems. These problems have been the focus of extensive research from the point of view of approximation algorithms and for both problems greedy-like algorithms have been proposed and analyzed. The priority algorithm definitions are general enough to capture a broad class of algorithms that can be characterized as greedy-like while still possible to derive non-trivial lower bounds on the approximability of the problems by algorithms in such a class. Our results are orthogonal to complexity considerations, and hence apply to algorithms that are not necessarily polynomial time.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.     

Simple On-Line Algorithms for the Maximum Disjoint Paths Problem

In this paper we study the classical problem of finding disjoint paths in graphs. This problem has been studied by a number of authors both for specific graphs and general classes of graphs. Whereas for specific graphs many (almost) matching upper and lower bounds are known for the competitiveness of on-line algorithms, not much is known about how well on-line algorithms can perform in the general setting. The best results obtained so far use the expansion of a network to measure the algorithms performance. We use a different parameter called the routing number that, as we will show, allows more precise results than the expansion. It enables us to prove tight upper and lower bounds for deterministic on-line algorithms. The upper bound is obtained by surprisingly simple greedy-like algorithms. Interestingly, our upper bound on the competitive ratio is even better than the best previous approximation ratio for off-line algorithms. Furthermore, we introduce a refined variant of the routing number and show that this variant allows us, for some classes of graphs, to construct on-line algorithms with a competitive ratio significantly below the best possible upper bound that could be obtained using the routing number or the expansion of a network only. We also show that our on-line algorithms can be transformed into efficient algorithms for the more general unsplittable flow problem.     

An Experimental Study of New and Known Online Packet Buffering Algorithms

We present the first experimental study of online packet buffering algorithms for network switches. We consider a basic scenario in which m queues of size B have to be maintained so as to maximize the packet throughput. For this model various online algorithms with competitive factors ranging between 2 and 1.5 were developed in the literature. We first develop a new 2-competitive online algorithm, called HSFOD, which is especially designed to perform well under real-world conditions. In our experimental study we have implemented all the proposed algorithms, including HSFOD, and tested them on packet traces from benchmark libraries. We have evaluated the experimentally observed competitiveness, the running times, memory requirements and actual packet throughput of the strategies. The tests were executed for varying values of m and B as well as varying switch speeds. It shows that greedy-like strategies and HSFOD perform best in practice.     

(Incremental) Priority Algorithms

We study the question of which optimization problems can be optimally or approximately solved by greedy or greedy-like algorithms. For definiteness, we limit the present discussion to some well-studied scheduling problems although the underlying issues apply in a much more general setting. Of course, the main benefit of greedy algorithms lies in both their conceptual simplicity and their computational efficiency. Based on the experience from online competitive analysis, it seems plausible that we should be able to derive approximation bounds for greedy-like algorithms exploiting only the conceptual simplicity of these algorithms. To this end, we need (and will provide) a precise definition of what we mean by greedy and greedy-like.     

无人机中继通信系统中信息传输调度算法研究

研究了将无人机作为通信中继平台对战区实施无线通信覆盖时的信息传输调度算法.首先介绍了几种基于信息特征(如优先级、长度、信息在系统总的占用时间等)的调度算法.为了克服传统调度算法的缺点,提出了一种改进的动态优先权调度(DPS,Dynamic Priority Scheduling)算法,将信息的优先级与接受系统服务的时间联系起来,动态调整信息的优先权,从而获得较小的系统平均时延,而且对不同信息又不失“公平性“.最后给出了几种调度算法的仿真结果,并对结果进行了分析.分析表明,动态优先权调度算法是一种比较适合无人机通信中继的实用调度算法.     

Toward a Model for Backtracking and Dynamic Programming

We propose a model called priority branching trees (pBT) for backtracking and dynamic programming algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as Interval Scheduling, Knapsack and Satisfiability.     

BubbleSearch: A simple heuristic for improving priority-based greedy algorithms

We introduce BubbleSearch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign values to elements in some fixed or adaptively determined order. BubbleSearch extends priority algorithms by selectively considering additional orders near an initial good ordering. While many notions of nearness are possible, we explore algorithms based on the Kendall-tau distance (also known as the BubbleSort distance) between permutations. Our contribution is to elucidate the BubbleSearch paradigm and experimentally demonstrate its effectiveness.     

Elastic threshold-based admission control for QoS satisfaction with reward optimization for servicing multiple priority classes in wireless networks

We analyze performance characteristics of a class of call admission control (CAC) algorithms designed for servicing multiple priority classes in wireless networks with the goal of quality of service (QoS) satisfaction and reward optimization. By reward, we mean some sort of “value” obtained by the system as a result of servicing multiple priority classes. In this paper we design and evaluate the performance of a new algorithm, elastic threshold-based CAC, in terms of the maximum reward obtainable with QoS satisfaction from servicing multiple priority classes with distinct QoS requirements, and compare it with existing partitioning, threshold, and spillover CAC algorithms. We also develop a heuristic-based search method to determine the best threshold-value sets used for multiple service classes by sequentially adjusting these thresholds based on the reward and rejection rate obtainable vs. QoS constraints of each service class. We demonstrate through test cases and simulation that elastic threshold-based CAC outperforms existing CAC algorithms for QoS satisfaction and reward optimization in solution optimality for serving multiple QoS service classes in wireless networks.     

优先队列的并行插入和删除

优先队列广泛地使用在许多并行算法中(例如,多处理机调度和某些组合优化算法)。在这些算法中,共享优先队列的存取冲突限制了加速比的提高。本文提出一种链表优先队列的并行插入和删除方法,具有较小并行开销和较大的并行度,并且保证和串行存取算法的优先顺序完全一致,即删除操作返回已经插入和正在插入的所有元素中的最佳元素。同时,我们还介绍了目前性能最好的堆的并行插入和删除算法,并对准和链表结构并行插入和删除算法的性能和适用范围进行了比较,进一步提出了散列结构的优先队列。在ENCORE Multimax520多处理机上的实验结果验证了我们的理论分析结果:使用链表结构的并行分枝限界算法性能上可获得很大提高。     

M1十M2／M／I/k系统输入队列调度算法性能比较

排队系统中优先级的划分方法主要有空间优先和时间优先两种类型。本文针对时间优先系统进行了分析，通过对缓冲器安全共享，缓冲器部分共享和分离缓冲器等三种缓冲器调度控制算法的分析比较，我们可以看出，分离缓冲器调度算法能够有效地减少实时顾客的失效概率，获得满意的控制效果，并且其实现的复杂度也较低。     

An exact schedulability test for fixed-priority preemptive mixed-criticality real-time systems

The current literature of fixed-priority scheduling algorithms relies on sufficient tests to determine if a set of mixed-criticality sporadic tasks is schedulable on a single processor. The drawback of these safe tests is their pessimism, a matter that could be solved if an exact schedulability analysis is used. However, because of the non-deterministic behavior of tasks in the mentioned setups, exact quantification of worst-case response times, needed for the test, is a difficult problem; more precisely, such a quantification needs evaluation of enormous sequences of job executions. The core problem is thus to merge such sequences to make the analysis practical. This paper, for the first time, gives an algorithm for exact worst-case response time characterization of mixed-criticality sporadic real-time tasks executing according to a given fixed-priority scheduler. We use a set of techniques which carefully consider the task properties and their relation to the worst scenarios to prune the analysis state space. We also show an interesting result that if an exact schedulability test is used, the Audsley’s optimal priority assignment algorithm is not applicable to the mixed-criticality case. Accordingly, we need new priority assignment algorithms to work with the exact test; we give a simple task priority assignment algorithm to this aim. The performance of the proposed exact test (in terms of time complexity) is examined and the effectiveness of some heuristic priority assignment algorithms using the test (in terms of the ratio of task sets which are deemed schedulable) are compared.     

The priority curve algorithm for video summarization

In this paper, we introduce the concept of a priority curve associated with a video. We then provide an algorithm that can use the priority curve to create a summary (of a desired length) of any video. The summary thus created exhibits nice continuity properties and also avoids repetition. We have implemented the priority curve algorithm (PriCA) and compared it with other summarization algorithms in the literature with respect to both performance and the output quality. The quality of summaries was evaluated by a group of 200 students in Naples, Italy, who watched soccer videos. We show that PriCA is faster than existing algorithms and also produces better quality summaries. We also briefly describe a soccer video summarization system we have built on using the PriCA architecture and various (classical) image processing algorithms.     

Fast and lock-free concurrent priority queues for multi-thread systems

We present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent priority queues are based on mutual exclusion. However, mutual exclusion causes blocking which has several drawbacks and degrades the overall performance of the system. Non-blocking algorithms avoid blocking, and several implementations have been proposed. Previously known non-blocking algorithms of priority queues did not perform well in practice because of their complexity, and they are often based on non-available atomic synchronization primitives. Our algorithm is based on the randomized sequential list structure called Skiplist, and a real-time extension of our algorithm is also described. In our performance evaluation we compare our algorithm with a well-representable set of earlier known implementations of priority queues. The experimental results clearly show that our lock-free implementation outperforms the other lock-based implementations in practical scenarios for 3 threads and more, both on fully concurrent as well as on pre-emptive systems.     

优先级有限时的单处理器静态优先级调度

静态优先级调度在实际应用中经常受到系统支持的优先级个数的影响,当任务个数多于系统优先级个数时,需要将几个任务优先级映射成一个系统优先级.这可能引起优先级映射问题,使映射前可调度的系统(任务集合)在映射后变得不可调度.解决这一问题需要减少时间复杂度的映射算法和判定映射后任务可调度性的充分必要条件主要存在3种映射算法:(1)按照任务优先级递减顺序进行映射的DPA(decreasing priority assignment)算法;(2)按照优先级递增顺序进行映射的IPA(Increasing priority assignment)算法;(3)阈值段间映射法(thresh01d segment mapping,简称TSM).描述了3种算法的实现和判定条件,论述并证明了算法特性,分析并通过仿真实验比较了算法的性能,最后总结了3种算法各自的适用场合.比较结果和结论对实时嵌入式系统的设计和实现具有一定的参考价值.     

The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks with static priority pre-emptive algorithms. We consider tasks which are characterized by a period, a hard deadline, a computation time and an offset (the time of the first request), where the offsets may be chosen by the scheduling algorithm, hence the denomination offset free systems.We study the rate monotonic and the deadline monotonic priority assignments for this kind of system and we compare the offset free systems and the asynchronous systems in terms of priority assignment. Hence, we show that the rate and the deadline monotonic priority assignments are not optimal for offset free systems.     

Multi-characteristics based data scheduling over the smart grid

In this paper, we propose multi-characteristics based data scheduling over smart grid. Three different pricing strategies are presented based on user priority and load rate. Then the corresponding novel scheduling algorithms are introduced by the proposed data priority and pricing strategies. The simulation experiments are carried out to evaluate the proposed algorithms based on trace data. And the results show that our methods can outperform the conventional method.     

Load shedding for multi-way stream joins based on arrival order patterns

We address the problem of load shedding for continuous multi-way join queries over multiple data streams. When the arrival rates of tuples from data streams exceed the system capacity, a load shedding algorithm drops some subset of input tuples to avoid system overloads. To decide which tuples to drop among the input tuples, most existing load shedding algorithms determine the priority of each input tuple based on the frequency or some historical statistics of its join attribute value, and then drop tuples with the lowest priority. However, those value-based algorithms cannot determine the priorities of tuples properly in environments where join attribute values are unique and each join attribute value occurs at most once in each data stream. In this paper, we propose a load shedding algorithm specifically designed for such environments. The proposed load shedding algorithm determines the priority of each tuple based on the order of streams in which its join attribute value appears, rather than its join attribute value itself. Consequently, the priorities of tuples can be determined effectively in environments where join attribute values are unique and do not repeat. The experimental results show that the proposed algorithm outperforms the existing algorithms in such environments in terms of effectiveness and efficiency.     

Priority algorithms for graph optimization problems

We continue the study of priority or “greedy-like” algorithms as initiated in Borodin et al. (2003) [10] and as extended to graph theoretic problems in Davis and Impagliazzo (2009) [12]. Graph theoretic problems pose some modeling problems that did not exist in the original applications of Borodin et al. and Angelopoulos and Borodin (2002) [3]. Following the work of Davis and Impagliazzo, we further clarify these concepts. In the graph theoretic setting, there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known “greedy algorithms”.     

多媒体服务器混合磁盘调度策略

基于多媒体服务器的性能要求，提出了一种自适应的混合磁盘调度策略DRT-window．它既能满足实时请求对实时性的要求，根据实时请求的截止期动态选择窗口大小；又能在其松弛度内尽努力(best-effort)地服务非实时请求，从而减少非实时请求的响应时间。DRT-window采用了两级层次调度方案：第一层为不同类型的请求采用各自适合的调度策略；第二层为混合请求调度嚣，混合调度第一层中的不同类型的请求。通过性能比较和理论证明，表明此混合磁盘调度策略能在保证实时请求无抖动执行的同时，尽量地减少非实时请求的响应时间。