Search

Your search keyword '"Zhang, Guochuan"' showing total 100 results
Start Over Author "Zhang, Guochuan" Publication Type Books
100 results on '"Zhang, Guochuan"'

45. Approximation Algorithms for Scheduling with a Variable Machine Maintenance.

Author

Luo, Wenchang, Chen, Lin, and Zhang, Guochuan

Abstract

In this paper, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and whose duration is a nondecreasing function of the starting time. We are asked not only to schedule the jobs but also the maintenance such that the total weighted job completion time is minimum. The problem is shown to be weakly NP-hard. In the case that the duration of the maintenance is a concave (and nondecreasing) function of its starting time, we provide two approximation algorithms with approximation ratio of 2 and at most ]> , respectively. [ABSTRACT FROM AUTHOR]

Published
2010
Full Text
View/download PDF

46. A Note on Online Scheduling for Jobs with Arbitrary Release Times.

Author

Ding, Jihuan and Zhang, Guochuan

Abstract

We investigate the problem of on-line scheduling for jobs with arbitrary release times on m identical parallel machines. The goal is to minimize the makespan. We derive a best possible online algorithm with competitive ratio of 2 for m = 2. For a special case that all the jobs have unit processing times, we prove that Algorithm LS has a tight bound of 3/2 for general m machines. [ABSTRACT FROM AUTHOR]

Published
2009
Full Text
View/download PDF

47. On-Line Multiple-Strip Packing.

Author

Ye, Deshi, Han, Xin, and Zhang, Guochuan

Abstract

We study the multiple-strip packing problem, in which the goal is to pack all the rectangles into m vertical strips of unit widths such that the maximum height among strips used is minimized. A number of on-line algorithms for this problem are proposed, in which the decision of delivering the rectangles to strips as well as packing the rectangles in strips must be done on-line. Both randomized and deterministic on-line algorithms are investigated, and all of them are guaranteed to have constant competitive ratios. [ABSTRACT FROM AUTHOR]

Published
2009
Full Text
View/download PDF

48. The Hardness of Selective Network Design for Bottleneck Routing Games.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Rangan, C. Pandu, Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Cai, Jin-Yi, Cooper, S. Barry, Zhu, Hong, Hou, Haiyang, and Zhang, Guochuan

Abstract

In this paper, motivated by the work of Azar et al. [3] we consider selective network design on bottleneck routing games. Assuming P ≠ NP we achieve the following results. For the unsplittable bottleneck games the trivial algorithm is a best possible approximation algorithm. For the k-splittable unweighted bottleneck games it is NP-hard to compute a best pure-strategy Nash equilibrium. Moreover no polynomial time algorithms can have a constant approximation ratio if the edge latency functions are continuous and non-decreasing. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

49. Heuristic Search for 2D NMR Alignment to Support Metabolite Identification.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Chen, Bo, Paterson, Mike, Zhang, Guochuan, Lee, Geun-Cheol, and de Ropp, Jeff

Abstract

For the problem of aligning two-dimensional NMR spectra of biological samples to determine if metabolite standards in a database can be excluded as possible constituents, we develop heuristic search algorithms that offer tremendous time savings when compared to manual methods. Xi et al [15] consider this problem and use statistical methods to reduce the search space and enumerate it. In this paper we consider the case when the statistical model is not available due to lack of data. We describe a simulated annealing algorithm and an algorithm that hybridizes simulated annealing with a shift neighborhood and a variant of reactive tabu search with a large neighborhood. Computational experiments based on data from physical experiments demonstrates that the hybrid is more effective than its constituents for runs with limited CPU time but that simulated annealing and the hybrid are roughly equal for longer runs. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

50. A Bijective Code for k-Trees with Linear Time Encoding and Decoding.

Author

Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Chen, Bo, Paterson, Mike, Zhang, Guochuan, Caminiti, Saverio, and Fusco, Emanuele G.

Abstract

The problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations between labeled trees and sequences of labels have been presented. k-trees are one of the most natural and interesting generalizations of trees and there is considerable interest in developing efficient tools to manipulate this class, since many NP-Complete problems have been shown to be polynomially solvable on k-trees and partial k-trees. In 1970 Rényi and Rényi generalized the Prüfer code to a subset of labeled k-trees; subsequently, non redundant codes that realize bijection between k-trees (or Rényi k-trees) and a well defined set of strings were produced. In this paper we introduce a new bijective code for labeled k-trees which, to the best of our knowledge, produces the first encoding and decoding algorithms running in linear time with respect to the size of the k-tree. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results