On Approximating a Scheduling Problem

Pierluigi Crescenzi (), Xiaotie Deng () and Christos H. Papadimitriou ()
Additional contact information
Pierluigi Crescenzi: Università degli Studi di Firenze
Xiaotie Deng: City University of Hong Kong
Christos H. Papadimitriou: University of California at Berkeley

Journal of Combinatorial Optimization, 2001, vol. 5, issue 3, No 2, 287-297

Abstract: Abstract Given a set of communication tasks (best described in terms of a weighted bipartite graph where one set of nodes denotes the senders, the other set the receivers, edges are communication tasks, and the weight of an edge is the time required for transmission), we wish to minimize the total time required for the completion of all communication tasks assuming that tasks can be preempted (that is, each edge can be subdivided into many edges with weights adding up to the edge's original weight) and that preemption comes with a cost. In this paper, we first prove that one cannot approximate this problem within a factor smaller than $$\frac{7}{6}$$ unless P=NP. It is known that a simple approximation algorithm achieves within a ratio of two (H. Choi and S.L. Hakimi, Algorithmica, vol. 3, pp. 223–245, 1988). However, our experimental results show that its performance is worse than the originally proposed heuristic algorithm (I.S. Gopal and C.K. Wong, IEEE Transactions on Communications, vol. 33, pp. 497–501, 1985). We devise a more sophisticated algorithm, called the potential function algorithm which, on the one hand, achieves a provable approximation ratio of two, and on the other hand, shows very good experimental performance. Moreover, the way in which our more sophisticated algorithm derives from the simple one, suggests a hierarchy of algorithms, all of which have a worst-case performance at most two, but which we suspect to have increasingly better performance, both in worst case and with actual instances.

Keywords: parallel computation; communication; bipartite graph; edge coloring (search for similar items in EconPapers)
Date: 2001
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/A:1011441109660 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:3:d:10.1023_a:1011441109660

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011441109660

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().