Distributed Online Frequency Assignment in Cellular Networks

A cellular network is generally modeled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multicoloring problem on a weighted graph, where the weight vector associated with the vertices models the number of calls to be served at the vertices and is assumed to change over time. In this paper, we develop a framework for studying distributed online frequency assignment in cellular networks. We present the first distributed online algorithms for this problem with proven bounds on their competitive ratios. We show a series of algorithms that use at each vertex information about increasingly larger neighborhoods of the vertex, and that achieve better competitive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms.     

Lower Bounds for Shellsort

We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg² n)/(lg lg n)²) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.     

Analysis of queueing policies in QoS switches

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the “best effort” approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst-case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.     

环形路网上带有服务时长的在线TSP问题

为了提高快递揽件的时效性,需要对快递车辆进行有效调度。针对环形路网上服务时长以及需求无法预知的揽件问题,本文提出了以服务总时间尽可能短为目标的环形路网上带有服务时长的在线旅行商问题。用在线算法分析了此问题竞争比的下界,设计了两个在线算法并分析了各自的竞争比,结果表明服务时长可以改善在线车的性能。最后通过简单算例对两个算法进行说明,本文研究结论可以为环形路网上的快递车辆实时调度提供指导。     

Hard satisfiable instances for DPLL-type algorithms

We address lower bounds on the time complexity of algorithms solving the propositional satisfiability problem. Namely, we consider two DPLL-type algorithms, enhanced with the unit clause and pure literal heuristics. Exponential lower bounds for solving satisfiability on provably satisfiable formulas are proven. Bibliography: 11 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 293, 2002, pp. 139–148.This revised version was published online in April 2005 with a corrected cover date and article title.     

The k-Client Problem

Virtually all previous research in online algorithms has focused on single-threaded systems where only a single sequence of requests compete for system resources. To model multithreaded online systems, we define and analyze the k-client problem, a dual of the well-studied k-server problem. In the basic k-client problem, there is a single server and k clients, each of which generates a sequence of requests for service in a metric space. The crux of the problem is deciding which client's request the single server should service rather than which server should be used to service the current request. We also consider variations where requests have nonzero processing times and where there are multiple servers as well as multiple clients.We evaluate the performance of algorithms using several cost functions including maximum completion time and average completion time. Two of the main results we derive are tight bounds on the performance of several commonly studied disk scheduling algorithms and lower bounds of on the competitive ratio of any online algorithm for the maximum completion time and average completion time cost functions when k is a power of 2. Most of our results are essentially identical for the maximum completion time and average completion time cost functions.     

First Hitting Time Analysis of the Independence Metropolis Sampler

In this paper, we study a special case of the Metropolis algorithm, the Independence Metropolis Sampler (IMS), in the finite state space case. The IMS is often used in designing components of more complex Markov Chain Monte Carlo algorithms. We present new results related to the first hitting time of individual states for the IMS. These results are expressed mostly in terms of the eigenvalues of the transition kernel. We derive a simple form formula for the mean first hitting time and we show tight lower and upper bounds on the mean first hitting time with the upper bound being the product of two factors: a “local” factor corresponding to the target state and a “global” factor, common to all the states, which is expressed in terms of the total variation distance between the target and the proposal probabilities. We also briefly discuss properties of the distribution of the first hitting time for the IMS and analyze its variance. We conclude by showing how some non-independence Metropolis–Hastings algorithms can perform better than the IMS and deriving general lower and upper bounds for the mean first hitting times of a Metropolis–Hastings algorithm.     

Multiple-type,two-dimensional bin packing problems: Applications and algorithms

In this paper we consider a class of bin selection and packing problems (BPP) in which potential bins are of various types, have two resource constraints, and the resource requirement for each object differs for each bin type. The problem is to select bins and assign the objects to bins so as to minimize the sum of bin costs while meeting the two resource constraints. This problem represents an extension of the classical two-dimensional BPP in which bins are homogeneous. Typical applications of this research include computer storage device selection with file assignment, robot selection with work station assignment, and computer processor selection with task assignment. Three solution algorithms have been developed and tested: a simple greedy heuristic, a method based onsimulated annealing (SA) and an exact algorithm based onColumn Generation with Branch and Bound (CG). An LP-based method for generating tight lower bounds was also developed (LB). Several hundred test problems based on computer storage device selection and file assignment were generated and solved. The heuristic solved problems up to 100 objects in less than a second; average solution value was within about 3% of the optimum. SA improved solutions to an average gap of less than 1% but a significant increase in computing time. LB produced average lower bounds within 3% of optimum within a few seconds. CG is practical for small to moderately-sized problems — possibly as many as 50 objects.     

The flow circulation sharing problem

The flow circulation sharing problem is defined as a network flow circulation problem with a maximin objective function. The arcs in the network are partitioned into regular arcs and tradeoff arcs where each tradeoff arc has a non-decreasing tradeoff function associated with it. All arcs have lower and upper bounds on their flow while the value of the smallest tradeoff function is maximized. The model is useful in equitable resource allocation problems over time which is illustrated in a coal strike example and a submarine assignment example. Some properties including optimality conditions are developed. Each cut in the network defines a knapsack sharing problem which leads to an optimality condition similar to the max flow/min cut theorem. An efficient algorithm for both the continuous and integer versions of the flow circulation sharing problem is developed and computational experience given. In addition, efficient algorithms are developed for problems where some of the arcs have infinite flow upper bounds.     

Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm

In this paper we consider algorithms to compute bounds of the A-norm of the error in the preconditioned conjugate gradient (PCG) algorithm. We extend to PCG formulas that were given in an earlier paper [8]. We give numerical experiments which show that good upper and lower bounds can be obtained provided estimates of the lowest and largest eigenvalues of the preconditioned matrix are given or adaptively computed. This revised version was published online in August 2006 with corrections to the Cover Date.     

Online time-constrained scheduling in linear and ring networks

We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002) [3]. In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios.     

Single machine scheduling with flow time and earliness penalties

This paper considers the problem of schedulingn jobs on a single machine to minimize the total cost incurred by their respective flow time and earliness penalties. It is assumed that each job has a due date that must be met, and that preemptions are not allowed. The problem is formulated as a dynamic program (DP) and solved with a reaching algorithm that exploits a series of dominance properties and efficiently generated bounds. A major factor underlying the effectiveness of the approach is the use of a greedy randomized adaptive search procedure (GRASP) to construct high quality feasible solutions. These solutions serve as upper bounds on the optimum, and permit a predominant portion of the state space to be fathomed during the DP recursion.To evaluate the performance of the algorithm, an experimental design involving over 240 randomly generated problems was followed. The test results indicate that problems with up to 30 jobs can be readily solved on a microcomputer in less than 12 minutes. This represents a significant improvement over previously reported results for both dynamic programming and mixed integer linear programming approaches.     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000     

Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds

Resource-constrained project scheduling under a net present value objective attracts growing interest. Because this is an NP-hard problem, it is unlikely that optimum solutions can be computed for large instances within reasonable computation time. Thus, heuristics have become a popular research field. Up to now, however, upper bounds are not well researched. Therefore, most researchers evaluate their heuristics on the basis of a best known lower bound, but it is unclear how good the performance really is. With this contribution we close this gap and derive tight upper bounds on the basis of a Lagrangian relaxation of the resource constraints. We also use this approach as a basis for a heuristic and show that our heuristic as well as the cash flow weight heuristic proposed by Baroum and Patterson yield solutions very close to the optimum result. Furthermore, we discuss the proper choice of a test-bed and emphasize that discount rates must be carefully chosen to give realistic instances.     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

Scheduling unit-time tasks in renewable resource constrained flowshops

In this paper we address the problem of scheduling unit time jobs in a flowshop to minimize makespan under a discrete renewable resource constraint. We propose algorithms having complexityO(n) for special cases of two machine and three machine problems. For the three machineN P-hard problem we develop a branch and bound procedure and several upper and lower bounds. We test the efficiency of the procedure and report our computational experience.Suna Kondakci was a visiting assistant professor at the Industrial Engineering Department, Purdue University, when the paper was revised.     

Efficient branch-and-bound algorithms for weighted MAX-2-SAT

MAX-2-SAT is one of the representative combinatorial problems and is known to be NP-hard. Given a set of m clauses on n propositional variables, where each clause contains at most two literals and is weighted by a positive real, MAX-2-SAT asks to find a truth assignment that maximizes the total weight of satisfied clauses. In this paper, we propose branch-and-bound exact algorithms for MAX-2-SAT utilizing three kinds of lower bounds. All lower bounds are based on a directed graph that represents conflicts among clauses, and two of them use a set covering representation of MAX-2-SAT. Computational comparisons on benchmark instances disclose that these algorithms are highly effective in reducing the number of search tree nodes as well as the computation time.     

Optimizing cost flows by edge cost and capacity upgrade

We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost.

The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ,>0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+δ and 1+, respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/(δ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities.     

Overflow and losses in a network queue with a self-similar input

This paper considers a discrete time queuing system that models a communication network multiplexer which is fed by a self-similar packet traffic. The model has a finite buffer of size h, a number of servers with unit service time, and an input traffic which is an aggregation of independent source-active periods having Pareto-distributed lengths and arriving as Poisson batches. The new asymptotic upper and lower bounds to the buffer-overflow and packet-loss probabilities P are obtained. The bounds give an exact asymptotic of log P/log h when h → to ∞. These bounds decay algebraically slow with buffer-size growth and exponentially fast with excess of channel capacity over traffic rate. Such behavior of the probabilities shows that one can better combat traffic losses in communication networks by increasing channel capacity rather than buffer size. A comparison of the obtained bounds and the known upper and lower bounds is done. This revised version was published online in June 2006 with corrections to the Cover Date.     

On error bounds for lower semicontinuous functions

We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f. Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002