Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks | SpringerLink
Skip to main content
Springer Nature Link
Log in

Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks

  • Conference paper
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX 2008, RANDOM 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5171))

  • 1192 Accesses

Abstract

We consider the deadline problem and budget problem of the nonlinear time-cost tradeoff project scheduling model in a series-parallel activity network. We develop fully polynomial time approximation schemes for both problems using K-approximation sets and functions, together with series and parallel reductions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the Association for Computing Machinery 41, 153–180 (1994)

    MATH  MathSciNet  Google Scholar 

  2. Bein, W.W., Kamburowski, J., Stallmann, M.F.M.: Optimal reduction of two-terminal directed acyclic graphs. SIAM Journal on Computing 21, 1112–1129 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  3. De, P., Dunne, E.J., Ghosh, J.B., Wells, C.E.: Complexity of the discrete time-cost tradeoff problem for project networks. Operations Research 45, 302–306 (1997)

    MATH  MathSciNet  Google Scholar 

  4. Deineko, V.G., Woeginger, G.J.: Hardness of approximation of the discrete time-cost tradeoff problem. Operations Research Letters 29, 207–210 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  5. Frank, H., Frisch, I.T., Van Slyke, R., Chou, W.S.: Optimal design of centralized computer networks. Networks 1, 43–58 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  6. Halman, N., Klabjan, D., Li, C.-L., Orlin, J., Simchi-Levi, D.: Fully polynomial time approximation schemes for stochastic dynamic programs. In: Proceedings of the Nineteenth ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 700–709 (2008)

    Google Scholar 

  7. Halman, N., Klabjan, D., Mostagir, M., Orlin, J., Simchi-Levi, D.: A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Working paper submitted for publication. Massachusetts Institute of Technology, Cambridge (2006)

    Google Scholar 

  8. Hassin, R.: Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research 17, 36–42 (1992)

    MATH  MathSciNet  Google Scholar 

  9. Hindelang, T.J., Muth, J.F.: A dynamic programming algorithm for decision CPM networks. Operations Research 27, 225–241 (1979)

    Article  MATH  Google Scholar 

  10. Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms 7, 309–322 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  11. Rothfarb, B., Frank, H., Rosebbaum, D.M., Steiglitz, K., Kleitman, D.J.: Optimal design of offshore natural-gas pipeline systems. Operations Research 18, 992–1020 (1970)

    Google Scholar 

  12. Skutella, M.: Approximation algorithms for the discrete time-cost tradeoff problem. Mathematics of Operations Research 23, 909–929 (1998)

    MATH  MathSciNet  Google Scholar 

  13. Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series-parallel digraphs. SIAM Journal on Computing 11, 298–313 (1982)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Advanced Study, Princeton, NJ, and Massachusetts Institute of Technology,  , Cambridge, MA

    Nir Halman

  2. The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

    Chung-Lun Li

  3. Massachusetts Institute of Technology,  , Cambridge, MA

    David Simchi-Levi

Authors
  1. Nir Halman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chung-Lun Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Simchi-Levi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Ashish Goel Klaus Jansen José D. P. Rolim Ronitt Rubinfeld

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Halman, N., Li, CL., Simchi-Levi, D. (2008). Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-85363-3_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-85362-6

  • Online ISBN: 978-3-540-85363-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation