Skip to main content
Erschienen in: Theory of Computing Systems 2/2013

01.08.2013

Online Scheduling with Interval Conflicts

verfasst von: Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz

Erschienen in: Theory of Computing Systems | Ausgabe 2/2013

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(lgσ), where σ is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is \(2\left \lceil {\lg\sigma} \right \rceil \) in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Ω(lgσ), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Fußnoten
1
For an efficient implementation (in AC0), e.g. to use in routers, it suffices to extract the smallest bit that is set, using the bit-wise operations (i XOR (i−1)) AND i.
 
Literatur
1.
Zurück zum Zitat Awerbuch, B., Azar, Y., Plotkin, S.A.: Throughput-competitive on-line routing. In: 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 32–40 (1993) Awerbuch, B., Azar, Y., Plotkin, S.A.: Throughput-competitive on-line routing. In: 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 32–40 (1993)
2.
Zurück zum Zitat Awerbuch, B., Bartal, Y., Fiat, A., Rosén, A.: Competitive non-preemptive call control. In: Proc. 5th SODA, pp. 312–320 (1994) Awerbuch, B., Bartal, Y., Fiat, A., Rosén, A.: Competitive non-preemptive call control. In: Proc. 5th SODA, pp. 312–320 (1994)
3.
Zurück zum Zitat Bachmann, U.T., Halldórsson, M.M., Shachnai, H.: Online selection of intervals and t-intervals. In: Proc. 11th SWAT. Lecture Notes in Computer Science, vol. 6139, pp. 383–394 (2010) Bachmann, U.T., Halldórsson, M.M., Shachnai, H.: Online selection of intervals and t-intervals. In: Proc. 11th SWAT. Lecture Notes in Computer Science, vol. 6139, pp. 383–394 (2010)
4.
Zurück zum Zitat Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Shieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001) MathSciNetCrossRef Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Shieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001) MathSciNetCrossRef
5.
6.
Zurück zum Zitat Emek, Y., Halldórsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing and competitive scheduling of multi-part tasks. In: Proc. 29th PODC, pp. 440–449 (2010) Emek, Y., Halldórsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing and competitive scheduling of multi-part tasks. In: Proc. 29th PODC, pp. 440–449 (2010)
7.
Zurück zum Zitat Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935) Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
8.
Zurück zum Zitat Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) MATH Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) MATH
9.
Zurück zum Zitat Jaromczyk, J.W., Pezarski, A., Slusarek, M.: An optimal competitive algorithm for the minimal clique covering in circular arc graphs. In: Proc. 19th EWCG (2003) Jaromczyk, J.W., Pezarski, A., Slusarek, M.: An optimal competitive algorithm for the minimal clique covering in circular arc graphs. In: Proc. 19th EWCG (2003)
10.
Zurück zum Zitat Karger, D., Stein, C., Wein, J.: Scheduling algorithms. In: Atallah, M.J. (ed.) Algorithms and Theory of Computation Handbook. CRC Press, Boca Raton (1998) Karger, D., Stein, C., Wein, J.: Scheduling algorithms. In: Atallah, M.J. (ed.) Algorithms and Theory of Computation Handbook. CRC Press, Boca Raton (1998)
11.
Zurück zum Zitat Kesselman, A., Patt-Shamir, B., Scalosub, G.: Competitive buffer management with packet dependencies. In: Proc. 23rd IPDPS, pp. 1–12 (2009) Kesselman, A., Patt-Shamir, B., Scalosub, G.: Competitive buffer management with packet dependencies. In: Proc. 23rd IPDPS, pp. 1–12 (2009)
12.
Zurück zum Zitat Lipton, R., Tomkins, A.: Online interval scheduling. In: Proc. 5th SODA, pp. 302–311 (1994) Lipton, R., Tomkins, A.: Online interval scheduling. In: Proc. 5th SODA, pp. 302–311 (1994)
13.
Zurück zum Zitat Sgall, J.: On-line scheduling. In: Online Algorithms. Lecture Notes in Computer Science, vol. 1442, pp. 196–231 (1996) CrossRef Sgall, J.: On-line scheduling. In: Online Algorithms. Lecture Notes in Computer Science, vol. 1442, pp. 196–231 (1996) CrossRef
Metadaten
Titel
Online Scheduling with Interval Conflicts
verfasst von
Magnús M. Halldórsson
Boaz Patt-Shamir
Dror Rawitz
Publikationsdatum
01.08.2013
Verlag
Springer-Verlag
Erschienen in
Theory of Computing Systems / Ausgabe 2/2013
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-012-9408-1

Weitere Artikel der Ausgabe 2/2013

Theory of Computing Systems 2/2013 Zur Ausgabe

OriginalPaper

Nominal Monoids