STACS 2004 : 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004 : proceedings

This book constitutes the refereed proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, STACS 2004, held in Montpellier, France, in March 2004. The 54 revised full papers presented together with two invited contributions were carefully reviewed and selected from more than 200 submissions. The papers are organized in topical sections on structural complexity, graph algorithms, quantum computing, satisfiability - constraint satisfaction problems, scheduling, algorithms, networks, automata theory and words, path algorithms, cryptography, logic and formal languages, game theory and complexity, and algorithmic information. The Symposium On Theoretical Aspects Of Computer Science (stacs) Is Alt- Nately Held In France And In Germany. The Conference Of March 25–27, 2004 At The Corum, Montpellier Was The Twenty-?rst In This Series. Previous Meetings Took Place In Paris (1984), Saarbruc ̈ Ken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992),wurzburg ̈ (1993),caen(1994),munc ̈ Hen(1995),grenoble(1996),lub ̈ Eck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), Antibes (2002), And Berlin (2003). The Symposium Looks Back At A Remarkable Tradition Of Over 20 Years. The Interest In Stacs Has Been Increasing Continuously During Recent Years And Has Turned It Into One Of The Most Signi?cant Conferences In Theoretical Computer Science. The Stacs 2004 Call For Papers Led To More Than 200 Submissions From All Over The World. Thereviewingprocesswasextremelyhard:morethan800reviewsweredone. We Would Like To Thank The Program Committee And All External Referees For The Valuable Work They Put Into The Reviewing Process Of This Conference. We Had A Two-day Meeting For The Program Committee In Montpellier During November 21–22, 2003. Just 54 Papers (i.e., 27% Of The Submissions) Could Be Accepted, As We Wanted To Keep The Conference In Its Standard Format With Only Two Parallel Sessions. This Strict Selection Guaranteed The Very High Scienti?c Quality Of The Conference. Invited Lectures -- Approximation Schemes For Metric Clustering Problems -- Positional Determinacy Of Infinite Games -- Structural Complexity (i) -- Individual Communication Complexity -- The Complexity Of Satisfiability Problems Over Finite Lattices -- Constant Width Planar Computation Characterizes Acc0 -- Graph Algorithms (i) -- A Simple And Fast Approach For Solving Problems On Planar Graphs -- Sum-multicoloring On Paths -- Matching Algorithms Are Fast In Sparse Random Graphs -- Quantum Computations -- Algebraic Results On Quantum Automata -- Quantum Identification Of Boolean Oracles -- Pattern Inference And Statistics -- Local Limit Distributions In Pattern Statistics: Beyond The Markovian Models -- A Discontinuity In Pattern Inference -- Satisfiability – Constraint Satisfaction Problem -- Algorithms For Sat Based On Search In Hamming Balls -- Identifying Efficiently Solvable Cases Of Max Csp -- The Complexity Of Boolean Constraint Isomorphism -- Scheduling (i) --^ On Minimizing The Total Weighted Tardiness On A Single Machine -- Online Competitive Algorithms For Maximizing Weighted Throughput Of Unit Jobs -- Optimal And Online Preemptive Scheduling On Uniformly Related Machines -- Algorithms -- Parallel Prefetching And Caching Is Hard -- Strongly Stable Matchings In Time O(nm) And Extension To The Hospitals-residents Problem -- Approximation Algorithms For Minimizing Average Distortion -- Networks (i) -- Digraphs Exploration With Little Memory -- Approximate Path Coloring With Applications To Wavelength Assignment In Wdm Optical Networks -- An Algorithmic View On Ovsf Code Assignment -- Automata Theory And Words -- The Syntactic Graph Of A Sofic Shift -- Periodicity And Unbordered Words -- Desert Automata And The Finite Substitution Problem -- Structural Complexity (ii) -- Satisfiability Problems Complete For Deterministic Logarithmic Space --^ A Logspace Approximation Scheme For The Shortest Path Problem For Graphs With Bounded Independence Number -- The Minimal Logically-defined Np-complete Problem -- Path Algorithms -- Solving The 2-disjoint Paths Problem In Nearly Linear Time -- Simpler Computation Of Single-source Shortest Paths In Linear Average Time -- Cryptography -- Lattices With Many Cycles Are Dense -- Automata-based Analysis Of Recursive Cryptographic Protocols -- Networks (ii) -- On Minimum Circular Arrangement -- Integral Symmetric 2-commodity Flows -- Efficient Algorithms For Low-energy Bounded-hop Broadcast In Ad-hoc Wireless Networks -- Logic And Formal Languages -- On The Expressiveness Of Deterministic Transducers Over Infinite Trees -- Definability And Regularity In Automatic Structures -- Active Context-free Games -- Graphs Algorithms (ii) -- Worst Case Performance Of An Approximation Algorithm For Asymmetric Tsp -- On Visibility Representation Of Plane Graphs --^ Topology Matters: Smoothed Competitiveness Of Metrical Task Systems -- Game Theory And Complexity -- A Randomized Competitive Algorithm For Evaluating Priced And/or Trees -- The Plurality Problem With Three Colors -- A Measured Collapse Of The Modal ?-calculus Alternation Hierarchy -- Networks (iii) -- An Information Theoretic Lower Bound For Broadcasting In Radio Networks -- A New Model For Selfish Routing -- Broadcast In The Rendezvous Model -- Structural Complexity (iii) -- Time-space Tradeoff In Derandomizing Probabilistic Logspace -- What Can Be Efficiently Reduced To The K-random Strings? -- Regular Language Matching And Other Decidable Cases Of The Satisfiability Problem For Constraints Between Regular Open Terms -- Scheduling (ii) -- Deterministic Truthful Approximation Mechanisms For Scheduling Related Machines -- The Expected Competitive Ratio For Weighted Completion Time Scheduling -- Algorithmic Information --^ Effective Strong Dimension In Algorithmic Information And Computational Complexity -- A Lower Bound On The Competitive Ratio Of Truthful Auctions -- Errata To Stacs 2003 -- Errata To Analysis Of The Harmonic Algorithm For Three Servers. Volker Diekert, Michel Habib, Eds. Includes Bibliographical References And Index. Front Matter....Pages - Approximation Schemes for Metric Clustering Problems....Pages 1-3 Positional Determinacy of Infinite Games....Pages 4-18 Individual Communication Complexity....Pages 19-30 The Complexity of Satisfiability Problems over Finite Lattices....Pages 31-43 Constant Width Planar Computation Characterizes ACC 0 ....Pages 44-55 A Simple and Fast Approach for Solving Problems on Planar Graphs....Pages 56-67 Sum-Multicoloring on Paths....Pages 68-80 Matching Algorithms Are Fast in Sparse Random Graphs....Pages 81-92 Algebraic Results on Quantum Automata....Pages 93-104 Quantum Identification of Boolean Oracles....Pages 105-116 Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models....Pages 117-128 A Discontinuity in Pattern Inference....Pages 129-140 Algorithms for SAT Based on Search in Hamming Balls....Pages 141-151 Identifying Efficiently Solvable Cases of Max CSP....Pages 152-163 The Complexity of Boolean Constraint Isomorphism....Pages 164-175 On Minimizing the Total Weighted Tardiness on a Single Machine....Pages 176-186 Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs....Pages 187-198 Optimal and Online Preemptive Scheduling on Uniformly Related Machines....Pages 199-210 Parallel Prefetching and Caching Is Hard....Pages 211-221 Strongly Stable Matchings in Time O ( nm ) and Extension to the Hospitals-Residents Problem....Pages 222-233 Approximation Algorithms for Minimizing Average Distortion....Pages 234-245 Digraphs Exploration with Little Memory....Pages 246-257 Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks....Pages 258-269 An Algorithmic View on OVSF Code Assignment....Pages 270-281 The Syntactic Graph of a Sofic Shift....Pages 282-293 Periodicity and Unbordered Words....Pages 294-304 Desert Automata and the Finite Substitution Problem....Pages 305-316 Satisfiability Problems Complete for Deterministic Logarithmic Space....Pages 317-325 A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number....Pages 326-337 The Minimal Logically-Defined NP-Complete Problem....Pages 338-349 Solving the 2-Disjoint Paths Problem in Nearly Linear Time....Pages 350-361 Simpler Computation of Single-Source Shortest Paths in Linear Average Time....Pages 362-369 Lattices with Many Cycles Are Dense....Pages 370-381 Automata-Based Analysis of Recursive Cryptographic Protocols....Pages 382-393 On Minimum Circular Arrangement....Pages 394-405 Integral Symmetric 2-Commodity Flows....Pages 406-417 Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks....Pages 418-427 On the Expressiveness of Deterministic Transducers over Infinite Trees....Pages 428-439 Definability and Regularity in Automatic Structures....Pages 440-451 Active Context-Free Games....Pages 452-464 Worst Case Performance of an Approximation Algorithm for Asymmetric TSP....Pages 465-476 On Visibility Representation of Plane Graphs....Pages 477-488 Topology Matters: Smoothed Competitiveness of Metrical Task Systems....Pages 489-500 A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees....Pages 501-512 The Plurality Problem with Three Colors....Pages 513-521 A Measured Collapse of the Modal μ -Calculus Alternation Hierarchy....Pages 522-533 An Information Theoretic Lower Bound for Broadcasting in Radio Networks....Pages 534-546 A New Model for Selfish Routing....Pages 547-558 Broadcast in the Rendezvous Model....Pages 559-570 Time-Space Tradeoff in Derandomizing Probabilistic Logspace....Pages 571-583 What Can be Efficiently Reduced to the K-Random Strings?....Pages 584-595 Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms....Pages 596-607 Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines....Pages 608-619 The Expected Competitive Ratio for Weighted Completion Time Scheduling....Pages 620-631 Effective Strong Dimension in Algorithmic Information and Computational Complexity....Pages 632-643 A Lower Bound on the Competitive Ratio of Truthful Auctions....Pages 644-655 Errata to Analysis of the Harmonic Algorithm for Three Servers....Pages 656-656 Back Matter....Pages - The Symposium On Theoretical Aspects Of Computer Science (stacs) Is Alt- Nately Held In France And In Germany. The Conference Of March 25-27, 2004 At The Corum, Montpellier Was The Twenty-?rst In This Series. Previous Meetings Took Place In Paris (1984), Saarbruc · Ken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wurzburg · (1993), Caen(1994), Munc · Hen(1995), Grenoble(1996), Lub · Eck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), Antibes (2002), And Berlin (2003). The Symposium Looks Back At A Remarkable Tradition Of Over 20 Years. The Interest In Stacs Has Been Increasing Continuously During Recent Years And Has Turned It Into One Of The Most Signi?cant Conferences In Theoretical Computer Science. The Stacs 2004 Call For Papers Led To More Than 200 Submissions From All Over The World. Thereviewingprocesswasextremelyhard:morethan800reviewsweredone. We Would Like To Thank The Program Committee And All External Referees For The Valuable Work They Put Into The Reviewing Process Of This Conference. We Had A Two-day Meeting For The Program Committee In Montpellier During November 21-22, 2003. Just 54 Papers (i.e., 27% Of The Submissions) Could Be Accepted, As We Wanted To Keep The Conference In Its Standard Format With Only Two Parallel Sessions. This Strict Selection Guaranteed The Very High Scienti?c Quality Of The Conference. Problem statement and motivation. The problem of partitioning a data set into a small number of clusters of related items has a crucial role in many information retrieval and data analysis applications, such as web search and classification [5,6,22,11], or interpretation of experimental data in molecular biology [21].