[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Online Matching for Scheduling Problems

  • Conference paper
  • First Online:
STACS 99 (STACS 1999)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1563))

Included in the following conference series:

Abstract

In this work an alternative online variant of the matching problem in bipartite graphs is presented. It is motivated by a scheduling problem in an online environment. In such an environment, a task is unknown up to its disclosure. However, in that moment it is not necessary to take a decision on the service of that particular task. In reality, an online scheduler has to decide on how to use the current resources. Therefore, our problem is called online request server matching (ORSM). It differs substantially from the online bipartite matching problem of Karp et al. [KVV90]. Hence, the analysis of an optimal, deterministic online algorithm for the ORSM problem results in a smaller competitive ratio of 1.5.

We also introduce an extension to a weighted bipartite matching problem. A lower bound of √+1 /2 ≈ 1.618 and an upper bound of 2 is given for the competitive ratio.

Supported by DFG-Graduiertenkolleg “Parallele Rechnernetzwerke in der Produktionstechnik”, GRK 124/2-96. This work was partly supported by the EU ESPRIT Long Term Research Project 20244 (ALCOM-IT).

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.

    Google Scholar 

  2. Ethan Bernstein and Sridhar Rajagopalan. The roommates problem: Online matching on general graphs. Technical Report CSD-93-757, University of California, Berkeley, CS Department, 1993.

    Google Scholar 

  3. Jack Edmonds. Paths, trees, and flowers. Canadian Journal on Mathematics, 7:449–467, 1965.

    MathSciNet  Google Scholar 

  4. Bala Kalyanasundaram and Kirk Pruhs. On-line network optimization problems. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms: The State of the Art, LNCS 1442, pages 268–280. Springer-Verlag, Berlin-Heidelberg-New York, 1998.

    Chapter  Google Scholar 

  5. Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 352–358, New York, 1990. ACM Press.

    Google Scholar 

  6. Marco Riedel. Online request server matching. Technical Report tr-ri-98-195, University of Paderborn, Germany, April 1998. available via: ftp://ftp.uni-paderborn.de/doc/techreports/Informatik/tr-ri-98-195.ps.Z

    Google Scholar 

  7. Jiří Sgall. On-line scheduling. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms: The State of the Art, LNCS 1442, pages 196–231. Springer-Verlag, Berlin-Heidelberg-New York, 1998.

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Heinz Nixdorf Institute, University of Paderborn, Germany

    Marco Riedel

Authors
  1. Marco Riedel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. FB IV - Informatik, Universität Trier, D-54286, Trier, Germany

    Christoph Meinel

  2. LIFL, Université de Lille I, Bătiment 3, F-59655, Villeneuve d’Ascq Cedex, France

    Sophie Tison

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Riedel, M. (1999). Online Matching for Scheduling Problems. In: Meinel, C., Tison, S. (eds) STACS 99. STACS 1999. Lecture Notes in Computer Science, vol 1563. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49116-3_54

Download citation

  • DOI: https://doi.org/10.1007/3-540-49116-3_54

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-65691-3

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

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation