A Tighter Extra-Resource Analysis of Online Deadline Scheduling

This paper is concerned with online algorithms for scheduling jobs with deadlines on a single processor. It has been known for long that unless the system is underloaded, no online scheduling algorithm can be 1-competitive, i.e., matching the performance of the optimal offline algorithm. Nevertheless, recent work has revealed that some online algorithms using a moderately faster processor (or extra processors) can guarantee very competitive performance Kalyanasundaram and Pruhs, 2000 or even be 1-competitive Koo et al., 2002; Lam and To, 2001. This paper takes a further step to investigate online scheduling algorithms with an even higher performance guarantee (i.e., better than 1-competitive algorithms) and in particular, presents an extra-resource analysis of the earliest-deadline-first strategy (EDF) with respect to such a higher performance guarantee.A preliminary version of this paper has been accepted by The Australian Theory Symposium on Computing, 2004.This research was supported in part by Hong Kong RGC Grant HKU-7024/01E.     

(1+ε)-competitive algorithm for online OVSF code assignment with resource augmentation

This paper studies the online Orthogonal Variable Spreading Factor (OVSF) code assignment problem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270–281, 2004). We propose a (1+1/α)-competitive algorithm with help of (1+?α?)lg^? h trees for the height h of the OVSF code tree and any α≥1. In other words, it is a (1+ε)-competitive algorithm with help of (1+?1/ε?)lg^? h trees for any constant 0<ε≤1. In the case of α=1 (or ε=1), we obtain a 2-competitive algorithm with 2lg^? h trees, which substantially improves the previous resource of 3h/8+2 trees shown by Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358–367, 2009). In another aspect, if it is not necessary to bound the incurred cost for individual requests to a constant, an amortized (4/3+δ)-competitive algorithm with (11/4+4/(3δ)) trees for any 0<δ≤4/3 is also designed in Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358–367, 2009). The algorithm in this paper gives us a new trade-off between the competitive ratio and the resource augmentation when α≥3 (or ε≤1/3), although the incurred cost for individual requests is bounded to a constant.     

Shifting strategy for geometric graphs without?geometry

We give a simple framework which is an alternative to the celebrated and widely used shifting strategy of Hochbaum and Maass (J. ACM 32(1):103?C136, 1985) which has yielded efficient algorithms with good approximation bounds for numerous optimization problems in low-dimensional Euclidean space. Our framework does not require the input graph/metric to have a geometric realization??it only requires that the input graph satisfy some weak property referred to as growth boundedness. Growth bounded graphs form an important graph class that has been used to model wireless networks. We show how to apply the framework to obtain a polynomial time approximation scheme (PTAS) for the maximum (weighted) independent set problem on this important graph class; the problem is W[1]-complete. Via a more sophisticated application of our framework, we show how to obtain a PTAS for the maximum (weighted) independent set for intersection graphs of (low-dimensional) fat objects that are expressed without geometry. Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) and Chan (J. Algorithms 46(2):178?C189, 2003) independently gave a PTAS for maximum weighted independent set problem for intersection graphs of fat geometric objects, say ball graphs, which required a geometric representation of the input. Our result gives a positive answer to a question of Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) who asked if a PTAS for this problem can be obtained without access to a geometric representation.     

An improved distributed data aggregation scheduling in wireless sensor networks

This paper focuses on the distributed data aggregation collision-free scheduling problem, which is one of very important issues in wireless sensor networks. Bo et al. (Proc. IEEE INFOCOM, 2009) proposed an approximate distributed algorithm for the problem and Xu et al. (Proc. ACM FOWANC, 2009) proposed a centralized algorithm and its distributed implementation to generate a collision-free scheduling for the problem, which are the only two existing distributed algorithms. Unfortunately, there are a few mistakes in their performance analysis in Bo et al. (Proc. IEEE INFOCOM, 2009), and the distributed algorithm can not get the same latency as the centralized algorithm because the distributed implementation was not an accurate implementation of the centralized algorithm (Xu et al. in Proc. ACM FOWANC, 2009). According to those, we propose an improved distributed algorithm to generate a collision-free schedule for data aggregation in wireless sensor networks. Not an arbitrary tree in Bo et al. (Proc. IEEE INFOCOM, 2009) but a breadth first search tree (BFS) rooted at the sink node is adopted, the bounded latency 61R+5Δ?67 of the schedule is obtained, where R is the radius of the network with respect to the sink node and Δ is the maximum node degree. We also correct the latency bound of the schedule in Bo et al. (Proc. IEEE INFOCOM, 2009) as 61D+5Δ?67, where D is a diameter of the network and prove that our algorithm is more efficient than the algorithm (Bo et al. in Proc. IEEE INFOCOM, 2009). We also give a latency bound for the distributed implementation in Xu et al. (Proc. ACM FOWANC, 2009).     

Competitive analysis for make-to-order scheduling with reliable lead time quotation

This paper makes extended studies on the discrete problem of online scheduling and reliable lead time quotation (discrete Q-SLTQ) introduced by Keskinocak et al. (Manag. Sci. 47(2):264–279, 2001). We first relax the assumption on revenue function from a linear decreasing function to any decreasing function. We present an online deterministic strategy which is optimal in competitiveness for concave revenue functions. The above results are further extended to the continuous Q-SLTQ model where orders are released at arbitrary time points. For the discrete Q-SLTQ problem, if orders are with nonuniform lengths, we prove the nonexistence of online strategies with bounded competitive ratios; otherwise if orders are with unit length but various weights, we present an optimal online strategy.     

Approximation algorithm for uniform bounded facility location problem

The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0–1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+? for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756–765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424–436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.     

The power of “mapping the territory”. Why economists should become more aware of the performativity of their models

Economics is not simply about representing reality; it is also about shaping it, an approach encapsulated in Donald MacKenzie’s aphorism that economics is best conceived as an “engine, not as a camera” (MacKenzie and Millo (Am J Sociol 109(1):107–145, 2003). The making and application of economic theories and models contribute actively and intentionally towards the making of our social world, by encouraging, guiding and legitimizing actions and decisions, or discouraging others, and by steering them in certain directions. It follows that economists do not simply draw maps of the economic territory within their compass: they are not straightforwardly the cartographers of the economy, and cannot be seen as the disinterested observers that they commonly represent themselves to be, and indeed are often thought of as. Their theoretical work has or aims at practical consequences for the economy, and indeed for society at large, and their interests and influence are thus by no means confined to academia alone. This article calls for a discussion of the ethical responsibilities of economists, and of economics, and challenges the discipline properly to assume those responsibilities; and it concludes by considering the key questions—what makes a ‘good’ economic model; and what criteria should be used to distinguish the good models, and the ‘good ways’ of handling models and their results, from the bad ones. As far as epistemology, the methodology of research programmes and the relation of theory and (social) practice are concerned, the insights of mainly von Hayek (Br J Philos Sci 6(23):209–225, 1955, The pretence of knowledge. Lecture to the memory of Alfred Nobel, 1974; Individualism and economic order, University of Chicago Press, Chicago, pp 33–56, 1980a; Individualism and economic order, University of Chicago Press, Chicago, pp 57–76, 1980b; The theory of complex phenomena. Readings in the philosophy of social science, MIT Press, Cambridge, 1994) and Popper (e.g. The myth of the framework: in defence of science and rationality, Routledge, New York 1994a; Models, instruments, and truth. The status of the rationality principle in the social sciences, pp 154–184, 1994b) provide the background of my discussion of the mentioned issues.     

Are there more almost separable partitions than separable partitions?

A partition of a set of n points in d-dimensional space into p parts is called an (almost) separable partition if the convex hulls formed by the parts are (almost) pairwise disjoint. These two partition classes are the most encountered ones in clustering and other partition problems for high-dimensional points and their usefulness depends critically on the issue whether their numbers are small. The problem of bounding separable partitions has been well studied in the literature (Alon and Onn in Discrete Appl. Math. 91:39–51, 1999; Barnes et al. in Math. Program. 54:69–86, 1992; Harding in Proc. Edinb. Math. Soc. 15:285–289, 1967; Hwang et al. in SIAM J. Optim. 10:70–81, 1999; Hwang and Rothblum in J. Comb. Optim. 21:423–433, 2011a). In this paper, we prove that for d≤2 or p≤2, the maximum number of almost separable partitions is equal to the maximum number of separable partitions.     

Almost optimal solutions for bin coloring problems

In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT+2 and OPT+1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio. The research of this paper was partially supported by an NSF CAREER award CCF-0546509.     

A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP

We present a primal-dual ?log(n)?-approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. The previous algorithm for the problem (V.H. Nguyen and T.T Nguyen in Int. J. Math. Oper. Res. 4(3):294–301, 2012) which is not combinatorial, is based on the Held-Karp relaxation and heuristic methods such as the Frieze et al.’s heuristic (Frieze et al. in Networks 12:23–39, 1982) or the recent Asadpour et al.’s heuristic for the ATSP (Asadpour et al. in 21st ACM-SIAM symposium on discrete algorithms, 2010). Depending on which of the two heuristics is used, it gives respectively 1+?log(n)? and $3+ 8\frac{\log(n)}{\log(\log(n))}$ as an approximation ratio. Our algorithm achieves an approximation ratio of ?log(n)? which is weaker than $3+ 8\frac{\log(n)}{\log(\log(n))}$ but represents the first combinatorial approximation algorithm for the Asymmetric Prize-Collecting TSP.     

Randomized Online Scheduling with Delivery Times

We study one of the most basic online scheduling models, online one machine scheduling with delivery times where jobs arrive over time. We provide the first randomized algorithm for this model, show that it is 1.55370-competitive and show that this analysis is tight. The best possible deterministic algorithm is 1.61803-competitive. Our algorithm is a distribution between two deterministic algorithms. We show that any such algorithm is no better than 1.5-competitive. To our knowledge, this is the first lower bound proof for a distribution between two deterministic algorithms.     

Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems

We consider the max-bisection problem and the disjoint 2-catalog segmentation problem, two well-known NP-hard combinatorial optimization problems. For the first problem, we apply the semidefinite programming (SDP) relaxation and the RPR² technique of Feige and Langberg (J. Algorithms 60:1–23, 2006) to obtain a performance curve as a function of the ratio of the optimal SDP value over the total weight through finer analysis under the assumption of convexity of the RPR² function. This ratio is shown to be in the range of [0.5,1]. The performance curve implies better approximation performance when this ratio is away from 0.92, corresponding to the lowest point on this curve with the currently best approximation ratio of 0.7031 due to Feige and Langberg (J. Algorithms 60:1–23, 2006). For the second problem, similar technique results in an approximation ratio of 0.7469, improving the previously best known result 0.7317 due to Wu et al. (J. Ind. Manag. Optim. 8:117–126, 2012).     

Greedy algorithms for the profit-aware social team formation problem

Motivated by applications in online labor markets, we study the problem of forming multiple teams of experts in a social network to accomplish multiple tasks that require different combinations of skills. Our goal is to maximize the total profit of tasks that are completed by these teams subject to the capacity constraints of the experts. We study both the offline and online settings of the problem. For the offline problem, we present a simple and practical algorithm that improves upon previous results in many situations. For the online problem, we design competitive deterministic and randomized online algorithms. These are complemented by some hardness results in both settings.

     

Clustering with or without the approximation

We study algorithms for clustering data that were recently proposed by Balcan et al. (SODA’09: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1068–1077, 2009a) and that have already given rise to several follow-up papers. The input for the clustering problem consists of points in a metric space and a number k, specifying the desired number of clusters. The algorithms find a clustering that is provably close to a target clustering, provided that the instance has the “(1+α,ε)-property”, which means that the instance is such that all solutions to the k-median problem for which the objective value is at most (1+α) times the optimal objective value correspond to clusterings that misclassify at most an ε fraction of the points with respect to the target clustering. We investigate the theoretical and practical implications of their results. Our main contributions are as follows. First, we show that instances that have the (1+α,ε)-property and for which, additionally, the clusters in the target clustering are large, are easier than general instances: the algorithm proposed in Balcan et al. (SODA’09: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1068–1077, 2009a) is a constant factor approximation algorithm with an approximation guarantee that is better than the known hardness of approximation for general instances. Further, we show that it is NP-hard to check if an instance satisfies the (1+α,ε)-property for a given (α,ε); the algorithms in Balcan et al. (SODA’09: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1068–1077, 2009a) need such α and ε as input parameters, however. We propose ways to use their algorithms even if we do not know values of α and ε for which the assumption holds. Finally, we implement these methods and other popular methods, and test them on real world data sets. We find that on these data sets there are no α and ε so that the dataset has both (1+α,ε)-property and sufficiently large clusters in the target solution. For the general case where there are no assumptions about the cluster sizes, we show that on our data sets the performance guarantee proved by Balcan et a. (SODA’09: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1068–1077, 2009a) is meaningless for the values of α,ε for which the data set has the (1+α,ε)-property. The algorithm nonetheless gives reasonable results, although it is outperformed by other methods.     

Chromatic number of distance graphs generated by the sets {2,3,x,y}

Let D be a set of positive integers. The distance graph generated by D has all integers ? as the vertex set; two vertices are adjacent whenever their absolute difference falls in D. We completely determine the chromatic number for the distance graphs generated by the sets D={2,3,x,y} for all values x and y. The methods we use include the density of sequences with missing differences and the parameter involved in the so called “lonely runner conjecture”. Previous results on this problem include: For x and y being prime numbers, this problem was completely solved by Voigt and Walther (Discrete Appl. Math. 51:197–209, 1994); and other results for special integers of x and y were obtained by Kemnitz and Kolberg (Discrete Math. 191:113–123, 1998) and by Voigt and Walther (Discrete Math. 97:395–397, 1991).     

Reflections on knowledge-based approaches to the organization of production

Knowledge-based approaches to the firm offer valuable insights into some of the central issues of governance and organizational design—especially into long neglected problems of coordination. I start from the assumption that the fundamental problem of economic organization is reconciling efficiency in knowledge development with efficiency in knowledge application. The paper extends the knowledge-based view of the firm and knowledge integration approach to organizational capability that I outlined in earlier papers (Grant in Strategic Management Journal, 1996a; Grant in Journal of Management Studies 7(4)375–387, 1996b) and draws upon subsequent contributions to the literature. From this basis, I derive implications for the relative efficiencies of alternative institutions of economic organization and for the design of firm structures.     

Women on boards and firm performance

This study investigates the financial performance of Dutch companies both with and without women on their boards. The analysis extends earlier methods used in research by Catalyst (The bottom line: corporate performance and women’s representation on boards, 2007) and McKinsey (Women matter. Gender diversity, a corporate performance driver. McKinsey & Company, USA, 2007), two studies that are often cited in the literature, although, each has a number of methodological shortcomings. This article adds to the international debate, which is often normative, through examining 99 listed companies in the Dutch Female Board Index. Our results show that firms with women directors perform better than those without women on their boards.     

考虑订单类型的两台平行批处理机在线调度模型研究

探讨了两台平行批处理机的调度决策问题,着重考虑了订单具有不同加工类型、同一批次只能加工相同类型的订单以及机器批容量有限的调度情形。针对订单实时到达且需要立即决策是否接受的实际情景,运用在线理论构建了平行机批调度在线模型。证明了该问题的竞争比下界为2Bw/（1+√Bw）,其中B和w分别表示批容量和单个订单的最大完工收益。进而设计给出了收益阈值算法PT并证明其对于订单具有紧交货期限的情形竞争比为2（1+Bw）/（1+√Bw）;对于非紧交货期限的情形,证明了修正的PT算法具有竞争比为1+2（1+Bw）/（1+√Bw）。     

Equivalence of two conjectures on equitable coloring of graphs

A graph G is said to be equitably k-colorable if there exists a proper k-coloring of G such that the sizes of any two color classes differ by at most one. Let Δ(G) denote the maximum degree of a vertex in G. Two Brooks-type conjectures on equitable Δ(G)-colorability have been proposed in Chen and Yen (Discrete Math., 2011) and Kierstead and Kostochka (Combinatorica 30:201–216, 2010) independently. We prove the equivalence of these conjectures.     

A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation

Let \((MQP)\) be a general mixed-integer quadratic program that consists of minimizing a quadratic function \(f(x) = x^TQx +c^Tx\) subject to linear constraints. Our approach to solve \((MQP)\) is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem has additional variables \(y_{ij}\) , additional quadratic constraints \(y_{ij}=x_ix_j\) , a convex objective function, and a set of valid inequalities. Contrarily to the reformulation proposed in Billionnet et al. (Math Program 131(1):381–401, 2012), the equivalent problem cannot be directly solved by a standard solver. Here, we propose a new Branch and Bound process based on the relaxation of the non-convex constraints \(y_{ij}=x_ix_j\) to solve \((MQP)\) . Computational experiences are carried out on pure- and mixed-integer quadratic instances. The results show that the solution time of most of the considered instances with up to 60 variables is improved by our Branch and Bound algorithm in comparison with the approach of Billionnet et al. (2012) and with the general mixed-integer nonlinear solver BARON (Sahinidis and Tawarmalani, Global optimization of mixed-integer nonlinear programs, user’s manual, 2010).