Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Die bibliographische Datenbank LEABib

Suchen • Liste der Journale • Liste der Serien • Liste der Konferenzen • Ausgewählte Publikationen	Hilfe

Suche: Series=LNCS AND YEAR=2011

• Semidefinite programming and approximation algorithms: A survey
  Sanjeev Arora
  Lecture Notes in Computer Science 7074, 2011, pp. 6-9
• The School Bus Problem The School Bus Problem is an NP-hard vehicle routing problem in which the goal is to route buses that transport children to a school such that for each child, the distance travelled on the bus does not exceed the shortest distance from the child's home to the school by more than a given regret threshold. Subject to this constraint and bus capacity limit, the goal is to minimize the number of buses required. In this paper, we give a polynomial time 4-approximation algorithm when the children and school are located at vertices of a fixed tree. As a byproduct of our analysis, we show that the integrality gap of the natural set-cover formulation for this problem is also bounded by 4. We also present a constant approximation for the variant where we have a fixed number of buses to use, and the goal is to minimize the maximum regret.on trees
  Adrian Bock, Elyot Grant, Jochen Könemann, Laura Sanità
  Lecture Notes in Computer Science 7074, 2011, pp. 10-19
• Contraction-based Steiner tree approximations in practice
  Markus Chimani, Matthias Woste
  Lecture Notes in Computer Science 7074, 2011, pp. 40-49
• Covering and piercing disks with two centers
  Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin, Antoine Vigneron
  Lecture Notes in Computer Science 7074, 2011, pp. 50-59
• Generating realistic roofs over a rectilinear polygon
  Hee-Kap Ahn, Sang Won Bae, Christian Knauer, Mira Lee, Chan-Su Shin, Antoine Vigneron
  Lecture Notes in Computer Science 7074, 2011, pp. 60-69
• Computing the visibility polygon using few variables
  Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira
  Lecture Notes in Computer Science 7074, 2011, pp. 70-79
• Dominating induced matchings for P_7-free graphs in linear time
  Andreas Brandstädt, Raffaele Mosca
  Lecture Notes in Computer Science 7074, 2011, pp. 100-109
• Finding contractions and induced minors in chordal graphs via disjoint paths
  Rémy Belmonte, Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Marcin Kamiński, Daniël Paulusma
  Lecture Notes in Computer Science 7074, 2011, pp. 110-119
• Dynamic range majority data structures
  Amr Elmasry, Meng He, J. Ian Munro, Patrick K. Nicholson
  Lecture Notes in Computer Science 7074, 2011, pp. 150-159
• Animal testing
  Adrian Dumitrescu, Evan Hilscher
  Lecture Notes in Computer Science 7074, 2011, pp. 220-229
• Cutting out polygons with a circular saw
  Adrian Dumitrescu, Masud Hasan
  Lecture Notes in Computer Science 7074, 2011, pp. 230-239
• Angle-restricted Steiner arborescences for flow map layout
  Kevin Buchin, Bettina Speckmann, Kevin Verbeek
  Lecture Notes in Computer Science 7074, 2011, pp. 250-259
• Simultaneous embedding of embedded planar graphs
  Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati
  Lecture Notes in Computer Science 7074, 2011, pp. 271-280
• Linear-time algorithms for hole-free rectilinear proportional contact graph representations
  Muhammad Jawaherul Alam, Therese Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann, Stephen G. Kobourov
  Lecture Notes in Computer Science 7074, 2011, pp. 281-291
• Compact representation of posets
  Arash Farzan, Johannes Fischer
  Lecture Notes in Computer Science 7074, 2011, pp. 302-311
• Explicit array-based compact data structures for triangulations
  Luca Castelli Aleardi, Olivier Devillers
  Lecture Notes in Computer Science 7074, 2011, pp. 312-322
• External-memory multimaps
  Elaine Angelino, Michael T. Goodrich, Michael Mitzenmacher, Justin Thaler
  Lecture Notes in Computer Science 7074, 2011, pp. 384-394
• Verifying Nash equilibria in PageRank games on undirected web graphs
  David Avis, Kazuo Iwama, Daichi Paku
  Lecture Notes in Computer Science 7074, 2011, pp. 415-424
• Program size and temperature in self-assembly
  Ho-Lin Chen, David Doty, Shinnosuke Seki
  Lecture Notes in Computer Science 7074, 2011, pp. 445-453
• Algorithm for single allocation problem on hub-and-spoke networks in 2-dimensional plane
  Ryuta Ando, Tomomi Matsui
  Lecture Notes in Computer Science 7074, 2011, pp. 474-483
• On power-law distributed balls in bins and its applications to view size estimation
  Ioannis Atsonios, Olivier Beaumont, Nicolas Hanusse, Yusik Kim
  Lecture Notes in Computer Science 7074, 2011, pp. 504-513
• Edit distance to monotonicity in sliding windows
  Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, Jiangwei Pan, Hing-Fung Ting, Qin Zhang
  Lecture Notes in Computer Science 7074, 2011, pp. 564-573
• Folding equilateral plane graphs
  Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, Isaac Shapiro-Ellowitz
  Lecture Notes in Computer Science 7074, 2011, pp. 574-583
• Efficient algorithms for the weighted k-center problem on a real line
  Danny Z. Chen, Haitao Wang
  Lecture Notes in Computer Science 7074, 2011, pp. 584-593
• Outlier respecting points approximation
  Danny Z. Chen, Haitao Wang
  Lecture Notes in Computer Science 7074, 2011, pp. 594-603