Willkommen, schön sind Sie da!
Logo Ex Libris

Automata, Languages and Programming

  • E-Book (pdf)
  • 754 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
Inhalt Invited Talks.- Local Search: Simple, Successful, But Sometimes Sluggish.- When Conflicting Constraints Can Be Resolved - T... Weiterlesen
E-Books ganz einfach mit der kostenlosen Ex Libris-Reader-App lesen. Hiererhalten Sie Ihren Download-Link.
CHF 173.90
Download steht sofort bereit
Informationen zu E-Books
E-Books eignen sich auch für mobile Geräte (sehen Sie dazu die Anleitungen).
E-Books von Ex Libris sind mit Adobe DRM kopiergeschützt: Erfahren Sie mehr.
Weitere Informationen finden Sie hier.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

Inhalt

Invited Talks.- Local Search: Simple, Successful, But Sometimes Sluggish.- When Conflicting Constraints Can Be Resolved - The Lovász Local Lemma and Satisfiability.- Session 1-Track A. Combinatorial Optimization.- Plane Spanners of Maximum Degree Six.- The Positive Semidefinite Grothendieck Problem with Rank Constraint.- Cycle Detection and Correction.- Decomposition Width of Matroids.- Session 2-Track A1. Game Theory.- The Cooperative Game Theory Foundations of Network Bargaining Games.- On the Existence of Pure Nash Equilibria in Weighted Congestion Games.- On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions.- Mean-Payoff Games and Propositional Proofs.- Session 2-Track A2. Security.- Online Network Design with Outliers.- Efficient Completely Non-malleable Public Key Encryption.- Polynomial-Space Approximation of No-Signaling Provers.- From Secrecy to Soundness: Efficient Verification via Secure Computation.- Session 3-Track A1. Data Structures.- Mergeable Dictionaries.- Faster Algorithms for Semi-matching Problems (Extended Abstract).- Clustering with Diversity.- New Data Structures for Subgraph Connectivity.- Session 3-Track A2. Sorting & Hashing.- Tight Thresholds for Cuckoo Hashing via XORSAT.- Resource Oblivious Sorting on Multicores.- Interval Sorting.- Session 4-Track A. Graphs, Nets and Optimization.- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems.- Thresholded Covering Algorithms for Robust and Max-min Optimization.- Graph Homomorphisms with Complex Values: A Dichotomy Theorem.- Metrical Task Systems and the k-Server Problem on HSTs.- Session 5-Track A1. Scheduling.- Scheduling Periodic Tasks in a Hard Real-Time Environment.- Scalably Scheduling Power-Heterogeneous Processors.- Better Scalable Algorithms for Broadcast Scheduling.- Max-min Online Allocations with a Reordering Buffer.- Session 5-Track A2. Graphs & Hypergraphs.- Orientability of Random Hypergraphs and the Power of Multiple Choices.- On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs.- Dynamic Programming for Graphs on Surfaces.- Interval Graphs: Canonical Representation in Logspace.- Session 6-Track A. Best Paper Award.- Approximating the Partition Function of the Ferromagnetic Potts Model.- Session 7-Track A. Algebraic Problems.- On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors.- On Sums of Roots of Unity.- Exponential Time Complexity of the Permanent and the Tutte Polynomial.- On Approximate Horn Formula Minimization.- Session 8-Track A. Networks & Communication Complexity.- Choosing, Agreeing, and Eliminating in Communication Complexity.- Additive Spanners in Nearly Quadratic Time.- Composition Theorems in Communication Complexity.- Network Design via Core Detouring for Problems without a Core.- Session 9-Track A1. Complexity & Automata.- Weak Completeness Notions for Exponential Time.- Efficient Evaluation of Nondeterministic Automata Using Factorization Forests.- On the Complexity of Searching in Trees: Average-Case Minimization.- Session 9-Track A2. Finding & Testing.- Finding Is as Easy as Detecting for Quantum Walks.- Improved Constructions for Non-adaptive Threshold Group Testing.- Testing Non-uniform k-Wise Independent Distributions over Product Spaces.- Session 10-Track A1. Approximations.- A Sublogarithmic Approximation for Highway and Tollbooth Pricing.- Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm.- Cell Probe Lower Bounds and Approximations for Range Mode.- SDP Gaps for 2-to-1 and Other Label-Cover Variants.- Session 10-Track A2. Streaming & Preprocessing.- Data Stream Algorithms for Codeword Testing.- Streaming Algorithms for Independent Sets.- Preprocessing of Min Ones Problems: A Dichotomy.- Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems.- Session 11-Track A1. Adaptive, Knowledge & Optimality.- Optimal Trade-Offs for Succinct String Indexes.- Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.- Concurrent Knowledge Extraction in the Public-Key Model.- Session 11-Track A2. Covering, Graphs & Independence.- On the k-Independence Required by Linear Probing and Minwise Independence.- Covering and Packing in Linear Space.- Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs.

Produktinformationen

Titel: Automata, Languages and Programming
Untertitel: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I
Editor:
EAN: 9783642141652
Format: E-Book (pdf)
Hersteller: Springer Berlin Heidelberg
Genre: IT & Internet
Veröffentlichung: 05.07.2010
Digitaler Kopierschutz: Wasserzeichen
Dateigrösse: 11.9 MB
Anzahl Seiten: 754

Weitere Bände aus der Buchreihe "Lecture Notes in Computer Science"