Klaus Jansen Knihy

This collection features a range of contributed talks covering various topics in approximation algorithms and network design. It includes discussions on designing networks to support fast restoration, simultaneous source location, and computationally-feasible truthful auctions for convex bundles. The book addresses randomized approximation algorithms for set multicover problems, particularly in the context of reverse engineering protein and gene networks. Key topics also include a 3/4-approximation algorithm for the maximum asymmetric traveling salesman problem, maximum coverage with group budget constraints, and the greedy algorithm for minimum common string partitioning. Further exploration includes approximating additive distortion in line metrics, polylogarithmic inapproximability of the radio broadcast problem, and auction-based market equilibrium algorithms. The text discusses cost-sharing mechanisms for network design, approximation schemes for broadcasting in heterogeneous networks, and convergence issues in competitive games. Other significant contributions involve semidefinite relaxations for linear ordering problems, min-max multiway cuts, and the chromatic number of random regular graphs. The collection also delves into estimating distances to monotone functions, edge coloring with delays, and robust locally testable codes. Topics such as stateful implementations of random functions, strong refutation heuristics

The Workshop on Approximation and Online Algorithms (WAOA 2003) focused on the design and analysis of algorithms for online and computationally hard problems. Both kinds of problems have a large number of applications ar- ing from a variety of ? elds. The workshop also covered experimental research on approximation and online algorithms. WAOA 2003 took place in Budapest, Hungary, from September 16 to September 18. The workshop was part of the ALGO 2003 event, which also hosted ESA 2003, WABI 2003, and ATMOS 2003. TopicsofinterestforWAOA2003were: competitiveanalysis, inapproximab- ityresults, randomizationtechniques, approximationclasses, scheduling, coloring and partitioning, cuts and connectivity, packing and covering, geometric pr- lems, network design, and applications to game theory and ? nancial problems. In response to our call for papers we received 41 submissions. Each submission was reviewed by at least 3 referees, who judged the papers on originality, quality, and consistency with the topics of the conference. Based on these reviews the program committee selected 19 papers for presentation at the workshop and for publication in this proceedings. This volume contains the 19 selected papers and 5 invited abstracts from an ARACNE minisymposium which took place as part of WAOA.

 This book constitutes the refereed proceedings of the Second International Workshop on Experimental and Efficient Algorithms, WEA 2003, held in Ascona, Switzerland in May 2003. The 19 revised full papers presented together with 3 invited contributions were carefully reviewed and selected from 40 submissions. The focus of the volume is on applications of efficient algorithms for combinatorial problems.

This book constitutes the refereed proceedings of the International Workshop on Approximation Algorithms for Combinatorical Optimization, APPROX'98, held in conjunction with ICALP'98 in Aalborg, Denmark, in July 1998. The volume presents 14 revised full papers together with three invited papers selected from 37 submissions. The papers address the design and analysis of approximation algorithms, inapproximability results, on-line problems, randomization techniques, average-case analysis, approximation classes, scheduling problems, routing and flow problems, coloring and partitioning, cuts and connectivity, packing and covering, geometric problems, network design, and various applications.

Woraus besteht die Sonne? Können wir den Mittelpunkt der Erde erreichen? Warum schmeckt man bei einer Erkältung nichts mehr? Wie orientieren sich Zugvögel? Was ist ein Regenwald? Wie fliegt ein Hubschrauber? Wer waren die Wikinger?Fragen über Fragen - und dieses Taschenbuch gibt die Antworten.Spannende Themen aus den Wissensgebieten-Erde und Weltall-Menschen, Tiere, Pflanzen-Wissenschaft und Technik-Geschichte, Kunst und Kulturladen zum Schmökern und Nachschlagen ein.Wieso? Weshalb? Warum? Wer nicht fragt, bleibt dumm!Mit Personen- und Sachregister zum Nachschlagen.

Gegenstand dieses Lehrbuchs ist die Behandlung schwer lösbarer diskreter Optimierungsprobleme. Im ersten Teil werden schnelle Algorithmen vorgestellt, die solche Probleme näherungsweise lösen können. Der zweite Teil behandelt Komplexitätstheorie und Nichtapproximierbarkeit von Optimierungsproblemen. Das Lehrbuch enthält zudem zahlreiche Anwendungsbeispiele, Übungsaufgaben, Illustrationen und Abschnitte über Grundlagen wie etwa die Turingmaschine.