Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 1/2015

01.01.2015

Advice Complexity of Maximum Independent set in Sparse and Bipartite Graphs

verfasst von: Stefan Dobrev, Rastislav Královič, Richard Královič

Erschienen in: Theory of Computing Systems | Ausgabe 1/2015

Einloggen

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

search-config
loading …

Abstract

We study the advice complexity of the online version of the Maximum Independent Set problem, restricted to the sparse, and bipartite graphs, respectively. We show that for sparse graphs, constant-sized advice is sufficient to obtain a constant competitive ratio, whereas for bipartite graphs, only competitive ratio Ω(log(n/a)/loglog(n/a)) can be obtained with an advice of size a > loglogn. However, competitive ratio O(logn) can be achieved with advice O(loglogn).
Vorheriger Artikel Approximating Spanning Trees with Few Branches
Nächster Artikel On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
Actually, the paper proves inapproximability of Maximum-Clique problem, where the aim is to find the subset of vertices with largest cardinality that form a clique. However, the two problems are obviously equivalent w.r.t. approximation.
 
2
Some works use a slightly relaxed definition by allowing an additive constant, i.e., the algorithm is c-competitive if there exists a constant α such that the cost of the worst-case output (for randomized algorithms the worst-case expected output) is at least 1/c⋅o p t − α.
 
3
A σ-bounded disc graph is an intersection graph of a set of discs in a plane, where the ratio of the radii of any two discs is at most σ.
 
4
although without any restrictions on the structure or size of the supergraph, one can always construct a “universal” supergraph that fools any deterministic algorithm; with randomized algorithms, however, the situation is more subtle (see [2])
 
5
As a remark we mention the lower bound 1.13747 logn colors needed for online coloring of bipartite graphs due to [3].
 
6
Since n is not known, a self-delimited encoding will be used, at a cost of small increase in the number of bits used.
 
7
note, however, that A d e t may behave differently afterwards
 
Literatur
1.
Bartal, Y., Fiat, A., Leonardi, S.: Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In: Stoc 1996, pp 531–540. ACM (1996)
2.
Bartal, Y., Fiat, A., Leonardi, S.: Lower bounds for on-line graph problems with application to on-line circuit and optical routing. SIAM J. Comput. 36(2), 354–393 (2006)CrossRefMATHMathSciNet
3.
Bianchi, M., Böckenhauer, H.-J., Hromkovic, J., Keller, L.: Online coloring of bipartite graphs with and without advice. Algorithmica 70(1), 92–111 (2014)CrossRefMathSciNet
4.
Böckenhauer, H.-J., Komm, D., Královic̆, R., Královic̆, R.: On the advice complexity of the k-server problem. In: ICALP 2011, LNCS, Vol. 6755, pp 207–218. Springer (2011)
5.
Boöckenhauer, H.-J., Komm, D., Královic̆, R., Královic̆, R., Mömke, T.: On the advice complexity of online problems. In: ISAAC 2009 LNCS, Vol. 5878, pp 331–340. Springer (2009)
6.
Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge Univ. Press (1998)
7.
Caragiannis, I., Fishkin, A.V., Kaklamanis, C., Papaioannou, E.: Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs. Discret. Appl. Math. 155(2), 119–136 (2007)CrossRefMATHMathSciNet
8.
Christodoulou, G., Zissimopoulos, V.: On-line maximum independent set in chordal graphs. J. Found. Comput. Decis. Sci. 30(4), 283–296 (2005)MATHMathSciNet
9.
Cieślik, I.: On-line graph coloring. Ph.D. Thesis, Jagiellonian University, Krakow, Poland (2004)
10.
Demange, M., Paradon, X., Paschos, V.T.: On-line maximum-order induces hereditary subgraph problems. In: SOFSEM 2008 LNCS, Vol. 1963, pp 327–335. Springer (2000)
11.
Dereniowski, D., Pelc, A.: Drawing maps with advice. J. Par. Distrib. Comput. 72(2), 132–143 (2012)CrossRefMATH
12.
Dobrev, S., Královic̆, R., Pardubská, D.: Measuring the problem-relevant information in input. ITA 43(3), 585–613 (2009)MATH
13.
Ebenlendr, T., Sgall, J.: Semi-online preemptive scheduling: One algorithm for all variants. Theory Comput. Syst. 48(3), 577–613 (2011)CrossRefMATHMathSciNet
14.
Emek, Y., Fraigniaud, P., Korman, A., Rosén, A.: Online computation with advice. Theor. Comput. Sci. 412(24), 2642–2656 (2011)CrossRefMATH
15.
16.
Fraigniaud, P., Gavoille, C., Ilcinkas, D., Pelc, A.: Distributed computing with advice: information sensitivity of graph coloring. Distrib. Comput. 21(6), 395–403 (2009)CrossRefMATH
17.
18.
Fraigniaud, P., Ilcinkas, D., Pelc, A.: Communication algorithms with advice. J. Comput. Syst. Sci. 76(3-4), 222–232 (2010)CrossRefMATHMathSciNet
19.
Fraigniaud, P., Korman, A., Lebhar, E.: Local mst computation with short advice. Theory Comput. Syst. 47(4), 920–933 (2010)CrossRefMATHMathSciNet
20.
Fusco, E.G., Pelc, A.: Trade-offs between the size of advice and broadcasting time in trees. Algorithmica 60(4), 719–734 (2011)CrossRefMATHMathSciNet
21.
22.
Halldórsson, M.M.: Online coloring known graphs. In: SODA 1999, pp 917–918. ACM/SIAM
23.
Halldórsson, M.M., Iwama, K., Miyazaki, S., Taketomi, S.: Online independent sets. Theor. Comput. Sci. 289(2), 953–962 (2002)CrossRefMATH
24.
25.
Hromkovic̆, J., Královic̆, R., Královic̆, R.: Information complexity of online problems. In: Mfcs 2010 LNCS, Vol. 6281, pp 24–36. Springer (2010)
26.
Ilcinkas, D., Kowalski, D.R., Pelc, A.: Fast radio broadcasting with advice. Theor. Comput. Sci. 411(14-15), 1544–1557 (2010)CrossRefMATHMathSciNet
27.
Kubale, M.: Graph colorings. In: Contemporary Mathematics, Vol. 352. AMS (2004)
28.
29.
Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs - a survey. Graphs and Combinatorics 20(1), 1–40 (2004)CrossRefMATHMathSciNet
30.
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)CrossRefMathSciNet
Metadaten
Titel
Advice Complexity of Maximum Independent set in Sparse and Bipartite Graphs
verfasst von
Stefan Dobrev
Rastislav Královič
Richard Královič
Publikationsdatum
01.01.2015
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 1/2015
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-014-9592-2

Weitere Artikel der Ausgabe 1/2015

Theory of Computing Systems 1/2015 Zur Ausgabe

OriginalPaper

Some Anomalies of Farsighted Strategic Behavior

EditorialNotes

Special Issue on Approximation and Online Algorithms

OriginalPaper

On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods

OriginalPaper

Approximation Algorithms for Fragmenting a Graph Against a Stochastically-Located Threat

OriginalPaper

On Online Algorithms with Advice for the k-Server Problem

OriginalPaper

A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines Without Preemption