Algorithms for hub label optimization

Maxim Babenko; Andrew V. Goldberg; Anupam Gupta; Viswanath Nagarajan

doi:10.1007/978-3-642-39206-1_7

Algorithms for hub label optimization

Maxim Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Cohen et al. developed an O(log n)-approximation algorithm for minimizing the total hub label size (ℓ₁ norm). We give O(log n)-approximation algorithms for the problems of minimizing the maximum label (ℓ_∞ norm) and minimizing ℓ_p and ℓ_q norms simultaneously..

Original language	English (US)
Title of host publication	Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Pages	69-80
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-39206-1_7
State	Published - 2013
Event	40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia Duration: Jul 8 2013 → Jul 12 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	7965 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
Country/Territory	Latvia
City	Riga
Period	7/8/13 → 7/12/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-39206-1_7

Cite this

Babenko, M., Goldberg, A. V., Gupta, A., & Nagarajan, V. (2013). Algorithms for hub label optimization. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings (PART 1 ed., pp. 69-80). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7965 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-39206-1_7

Algorithms for hub label optimization. / Babenko, Maxim; Goldberg, Andrew V.; Gupta, Anupam et al.
Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1. ed. 2013. p. 69-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7965 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Babenko, M, Goldberg, AV, Gupta, A & Nagarajan, V 2013, Algorithms for hub label optimization. in Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 7965 LNCS, pp. 69-80, 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013, Riga, Latvia, 7/8/13. https://doi.org/10.1007/978-3-642-39206-1_7

Babenko M, Goldberg AV, Gupta A, Nagarajan V. Algorithms for hub label optimization. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. 2013. p. 69-80. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-39206-1_7

@inproceedings{7fceac0798874e6c8fcd686a98a37017,

title = "Algorithms for hub label optimization",

abstract = "Cohen et al. developed an O(log n)-approximation algorithm for minimizing the total hub label size (ℓ1 norm). We give O(log n)-approximation algorithms for the problems of minimizing the maximum label (ℓ∞ norm) and minimizing ℓp and ℓq norms simultaneously..",

author = "Maxim Babenko and Goldberg, {Andrew V.} and Anupam Gupta and Viswanath Nagarajan",

year = "2013",

doi = "10.1007/978-3-642-39206-1_7",

language = "English (US)",

isbn = "9783642392054",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "69--80",

booktitle = "Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings",

edition = "PART 1",

note = "40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 ; Conference date: 08-07-2013 Through 12-07-2013",

}

TY - GEN

T1 - Algorithms for hub label optimization

AU - Babenko, Maxim

AU - Goldberg, Andrew V.

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

PY - 2013

Y1 - 2013

N2 - Cohen et al. developed an O(log n)-approximation algorithm for minimizing the total hub label size (ℓ1 norm). We give O(log n)-approximation algorithms for the problems of minimizing the maximum label (ℓ∞ norm) and minimizing ℓp and ℓq norms simultaneously..

AB - Cohen et al. developed an O(log n)-approximation algorithm for minimizing the total hub label size (ℓ1 norm). We give O(log n)-approximation algorithms for the problems of minimizing the maximum label (ℓ∞ norm) and minimizing ℓp and ℓq norms simultaneously..

UR - http://www.scopus.com/inward/record.url?scp=84880318819&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880318819&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_7

DO - 10.1007/978-3-642-39206-1_7

M3 - Conference contribution

AN - SCOPUS:84880318819

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 69

EP - 80

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -

Algorithms for hub label optimization

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this