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.     

Scheduling with Conflicts on Bipartite and Interval Graphs

In this paper, we consider the on-line scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that the set of all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. Our results focus on two special classes of graphs motivated by our applications: bipartite graphs and interval graphs. The cost function we use is maximum response time. In all of the upper bounds, we devise algorithms which maintain a set of invariants which bound the accumulation of jobs on cliques (in the case of bipartite graphs, edges) in the graph. The lower bounds show that the invariants maintained by the algorithms are tight to within a constant factor. For a specific graph which arises in the traffic intersection control problem, we show a simple algorithm which achieves the optimal competitive ratio.     

An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log² n) time withO(n ³) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.Research supported in part by NSF Grants CCR-9011214 and CCR-9205982.     

Randomized competitive algorithms for the list update problem

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.     

An efficient parallel algorithm for finding rectangular duals of plane triangular graphs

We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log² n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.This research was supported by NSF Grants CCR-9011214 and CCR-9205982.     

Bandwidth guaranteed multicast scheduling for virtual output queued packet switches

Multicast enables efficient data transmission from one source to multiple destinations, and has been playing an important role in Internet multimedia applications. Although several multicast scheduling schemes for packet switches have been proposed in the literature, they usually aim to achieve only short multicast latency and high throughput without considering bandwidth guarantees. However, fair bandwidth allocation is critical for the quality of service (QoS) of the network, and is necessary to support multicast applications requiring guaranteed performance services, such as online audio and video streaming. This paper addresses the issue of bandwidth guaranteed multicast scheduling on virtual output queued (VOQ) switches. We propose the Credit based Multicast Fair scheduling (CMF) algorithm, which aims at achieving not only short multicast latency but also fair bandwidth allocation. CMF uses a credit based strategy to guarantee the reserved bandwidth of an input port on each output port of the switch. It keeps track of the difference between the reserved bandwidth and actually received bandwidth, and minimizes the difference to ensure fairness. Moreover, in order to fully utilize the multicast capability provided by the switch, CMF lets a multicast packet simultaneously send transmission requests to multiple output ports. In this way, a multicast packet has more chances to be delivered to multiple destination output ports in the same time slot and thus to achieve short multicast latency. Extensive simulations are conducted to evaluate the performance of CMF, and the results demonstrate that CMF achieves the two design goals: fair bandwidth allocation and short multicast latency.     

Finding the closed partition of a planar graph

In this paper we consider the problem of finding aclosed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs inO(mn) time wherem is the number of directed edges andn is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that arecompact. We then build on this algorithm to obtain an O(n^1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.This work was supported in part by NSF Grant CCR 89-10707.     

Maximum weight k-independent set problem on permutation graphs

Based on a Directed Acyclic Graph approach, an O(kn ²) time sequential algorithm is presented to solve the maximum weight k-independent set problem on weighted-permutation graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. This problem has many applications in practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design and routing problem.     

基于图匹配的多处理机调度算法

本文对具有高通讯延迟的多处理机系统（机群系统）上的任务调度算法进行了研究，与以往算法主要考虑任务图的关键路径不同，本文给出了任务图的调度与其偶图匹配的对应关系，并由此提出了一种新的启发式算法，通过模拟试验显示本算法具有较好的调度效果。     

Improving exact algorithms for MAX-2-SAT

We study three new techniques that will speed up the branch-and-bound algorithm for the MAX-2-SAT problem: The first technique is a group of new lower bound functions for the algorithm and we show that these functions are admissible and consistently better than other known lower bound functions. The other two techniques are based on the strongly connected components of the implication graph of a 2CNF formula: One uses the graph to simplify the formula and the other uses the graph to design a new variable ordering. The experiments show that the simplification can reduce the size of the input substantially no matter what is the clause-to-variable ratio and that the new variable ordering performs much better when the clause-to-variable ratio is less than 2. A direct outcome of this research is a high-performance implementation of an exact algorithm for MAX-2-SAT which outperforms any implementation we know about in the same category. We also show that our implementation is a feasible and effective tool to solve large instances of the Max-Cut problem in graph theory.Preliminary results of this paper appeared in [20,21]. This research was supported in part by NSF under grant CCR-0098093.     

An effective scheduling scheme for multi-hop multicast in wireless mesh networks

With the utilization of concurrent transmission strategy, a throughput-enhanced scheduling scheme is devised for multicast service in wireless multi-hop mesh networks. Since the performance of a multicast mechanism is constrained in a wireless setting due to the interference among local wireless transmissions, the interference relationships are first characterized by introducing a graph transformation method. Based on the graph transformation, the multicast scheduling problem is converted to the graph coloring problem, and then a capacity greedy algorithm is designed to provide concurrent transmission scheduling so that the demanded multicast transmission rate can be achieved. Moreover, the necessary and sufficient conditions of multicast schedulable feasibility are derived. Through corresponding simulations, it is shown that the proposed strategy can enhance the throughput of wireless multi-hop multicast systems significantly.     

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

We present polylogarithmic approximations for the R|prec|C _max and R|prec|∑ _j w _j C _j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994). The first step in our algorithm for the R|prec|C _max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function. A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005. V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683. Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636.     

An effective scheduling scheme for multi-hop multicast in wireless mesh networks

With the utilization of concurrent transmission strategy, a throughput-enhanced scheduling scheme is devised for multicast service in wireless multi-hop mesh networks. Since the performance of a multicast mechanism is constrained in a wireless setting due to the interference among local wireless transmissions, the interference relationships are first characterized by introducing a graph transformation method. Based on the graph transformation, the multicast scheduling problem is converted to the graph coloring problem, and then a capacity greedy algorithm is designed to provide concurrent transmission scheduling so that the demanded multicast transmission rate can be achieved. Moreover, the necessary and sufficient conditions of multicast schedulable feasibility are derived. Through corresponding simulations, it is shown that the proposed strategy can enhance the throughput of wireless multi-hop multicast systems significantly.     

考虑缓冲区的自动生产单元的无死锁调度策略

在制造系统中,必须防止死锁的发生.本文提出了一种在制造系统(带有有限缓冲区)中搜索最优的无死锁调度的算法.为此首先介绍了死锁问题及其图论表示方法,然后在遗传算法的基础上,运用图论算法来保证无死锁的调度结果.为了保证遗传算法生成的调度策略能够满足所要求的约束,运用图论方法选择无死锁个体,或添加缓冲区,从而在基本保证了系统的主要性能指标的同时,得到系统可行的无死锁调度结果.最后给出了一个运用此方法解决死锁问题的实例.     

Nonblocking k-fold multicast networks

Multicast communication involves transmitting information from a single source to multiple destinations and is a requirement in high-performance networks. Current trends in networking applications indicate an increasing demand in future networks for multicast capability. Many multicast applications require not only multicast capability, but also predictable communication performance such as guaranteed multicast latency and bandwidth. In this paper, we present a design for a nonblocking k-fold multicast network, in which any destination node can be involved in up to k simultaneous multicast connections in a nonblocking manner. We also develop an efficient routing algorithm for the network. As can be seen, a k-fold multicast network has significantly lower network cost than that of k copies of ordinary 1-fold multicast networks and is a cost effective choice for supporting arbitrary multicast communication.     

基于TSP方法求解等待时间受限的置换流水车间调度

等待时间受限的置换流水车间调度问题要求工件在连续两个机器间的等待时间满足上限值约束.对此,分析了工件序列中相邻工件的加工持续时间及其上下界关系,并且提出一种启发式方法.首先,建立旅行商间题（TSP）以生成初始调度;然后,采用扩展插入方法优化调度解.为了衡量算法性能,给出问题下界的计算方法和相关评价指标,并通过数据实验验证了该启发式和下界计算方法的可行性和有效性.     

Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor Assignment

We consider the schedulability of a set of independent periodic tasks under fixed priority preemptive scheduling on homogeneous multiprocessor systems. Assuming there is no task migration between processors and each processor schedules tasks preemptively according to fixed priorities assigned by the Rate Monotonic policy, the scheduling problem reduces to assigning the set of tasks to disjoint processors in such a way that the Monotonic policy, the scheduling problem reduces to assigning the set of tasks to disjoint processors in such a way that the schedulability of the tasks on each processor can be guaranteed. In this paper we show that the worst case achievable utilization for such systems is between n(2^1/2-1) and (n+1)/(1+2^1/(n+1)), where n stands for the number of processors. The lower bound represents 41 percent of the total system capacity and the upper bound represents 50 to 66 percent depending on n. Practicality of the lower bound is demonstrated by proving it can be achieved using a First Fit scheduling algorithm.     

An optimal scheduling algorithm for an agent-based multicast strategy on irregular networks

This paper describes an agent-based approach for scheduling multiple multicast on wormhole switch-based networks with irregular topologies. Multicast/broadcast is an important communication pattern, with applications in collective communication operations such as barrier synchronization and global combining. Our approach assigns an agent to each subtree of switches such that the agents can exchange information efficiently and independently. The entire multicast problem is then recursively solved with each agent sending message to those switches that it is responsible for. In this way, communication is localized by the assignment of agents to subtrees. This idea can be easily generalized to multiple multicast since the order of message passing among agents can be interleaved for different multicasts. The key to the performance of this agent-based approach is the message-passing scheduling between agents and the destination processors. We propose an optimal scheduling algorithm, called ForwardInSwitch to solve this problem. We conduct extensive experiments to demonstrate the efficiency of our approach by comparing our results with SPCCO, a highly efficient multicast algorithm reported in literature. We found that SPCCO suffers link contention when the number of simultaneous multiple multicast becomes large. On the other hand, our agent-based approach achieves better performance in large cases.     

An Online Algorithm for the Dynamic Maximal Dense Tree Problem

Abstract. The Online Maximal Dense Tree problem is as follows: given a weighted directed graph and a source node, users issue online requests for connection to the source node. A request can either be accepted or rejected (the admission control decision). If the connection request is accepted, it must be connected to the source or to a node previously connected to the source (the routing decision). The objective is to maximize the total number of connections while keeping the connection density , i.e. the ratio of accepted requests to the weight of the spanning tree, sufficiently high. The primary motivation for the Maximal Dense Tree problem is the Online Capacitated Multicast admission control and routing problem. In the Online Capacitated Multicast problem, we are given a communication network with limited link capacities and a set of signal source nodes. Users generate online requests for connection to the signal sources, and the network administrator has to make the admission control and routing decisions. The goal of the network administrator is to maximize the total number of users connected subject to the network capacity constraints. The Online Maximal Dense Tree problem is also faced by a cable TV operator who wishes to connect as many customers as possible while keeping down the amount of wiring per customer. Informally, the Online Maximal Dense Tree algorithm must ``gamble' on certain geographic areas, connecting nodes which are unprofitable to start with, in the hope that eventually enough requests will arrive in its vicinity to make the investment profitable. In this paper we present a randomized online algorithm for the Maximal Dense Tree problem that guarantees acceptance of a (1- ɛ) factor of the requests accepted by the optimum offline algorithm with the expectation of density being at most polylogarithmically lower than that of the offline algorithm. This yields an online capacitated multicast algorithm whose throughput is only poly-logarithmically lower than that of the optimum offline algorithm. Previous work on multicast routing and maximal dense tree problems either made probabilistic assumptions or resulted in linear performance gaps with the offline algorithm. Attempts to solve the Online Maximal Dense Tree problem have also lead to the development of the first polylogarithmic approximation algorithms for the k -MST and the Prize Collecting Salesman problems [AABV].     

一种基于Ethernet新的可靠多播算法

可靠多播算法在并行处理中有着广泛的应用.文章在分析基于共享介质Ethernet的3种可靠多播算法的基础上,提出了一种新的可靠多播算法：MAK(multicast acknowledgment)多播算法,并且以实验数据验证了此算法的高效性.