Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques [[electronic resource] ] : 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA,USA, August 18-20, 2001 / / edited by Michel Goemans, Klaus Jansen, Jose D.P. Rolim, Luca Trevisan |
Edizione | [1st ed. 2001.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2001 |
Descrizione fisica | 1 online resource (IX, 296 p.) |
Disciplina | 004/.01/5114 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Mathematical analysis
Analysis (Mathematics) Computer programming Discrete mathematics Algorithms Numerical analysis Combinatorics Analysis Programming Techniques Discrete Mathematics Algorithm Analysis and Problem Complexity Numeric Computing |
ISBN | 3-540-44666-4 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Using Complex Semidefinite Programming for Approximating MAX E2-LIN3 -- Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems -- Web Search via Hub Synthesis -- Error-Correcting Codes and Pseudorandom Projections -- Order in Pseudorandomness -- Contributed Talks of APPROX -- Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows -- On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique -- Online Weighted Flow Time and Deadline Scheduling -- An Online Algorithm for the Postman Problem with a Small Penalty -- A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem -- Approximation Schemes for Ordered Vector Packing Problems -- Incremental Codes -- A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set -- Approximation Algorithms for Budget-Constrained Auctions -- Minimizing Average Completion of Dedicated Tasks and Interval Graphs -- A Greedy Facility Location Algorithm Analyzed Using Dual Fitting -- 0.863-Approximation Algorithm for MAX DICUT -- The Maximum Acyclic Subgraph Problem and Degree-3 Graphs -- Some Approximation Results for the Maximum Agreement Forest Problem -- Contributed Talks of RANDOM -- Near-optimum Universal Graphs for Graphs with Bounded Degrees -- On a Generalized Ruin Problem -- On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation -- Exact Sampling in Machine Scheduling Problems -- On Computing Ad-hoc Selective Families -- L Infinity Embeddings -- On Euclidean Embeddings and Bandwidth Minimization -- The Non-approximability of Non-Boolean Predicates -- On the Derandomization of Constant Depth Circuits -- Testing Parenthesis Languages -- Proclaiming Dictators and Juntas or Testing Boolean Formulae -- Equitable Coloring Extends Chernoff-Hoeffding Bounds. |
Record Nr. | UNISA-996465806303316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2001 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques : 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA,USA, August 18-20, 2001 / / edited by Michel Goemans, Klaus Jansen, Jose D.P. Rolim, Luca Trevisan |
Edizione | [1st ed. 2001.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2001 |
Descrizione fisica | 1 online resource (IX, 296 p.) |
Disciplina | 004/.01/5114 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Mathematical analysis
Computer programming Discrete mathematics Algorithms Numerical analysis Analysis Programming Techniques Discrete Mathematics Numerical Analysis |
ISBN | 3-540-44666-4 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Using Complex Semidefinite Programming for Approximating MAX E2-LIN3 -- Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems -- Web Search via Hub Synthesis -- Error-Correcting Codes and Pseudorandom Projections -- Order in Pseudorandomness -- Contributed Talks of APPROX -- Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows -- On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique -- Online Weighted Flow Time and Deadline Scheduling -- An Online Algorithm for the Postman Problem with a Small Penalty -- A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem -- Approximation Schemes for Ordered Vector Packing Problems -- Incremental Codes -- A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set -- Approximation Algorithms for Budget-Constrained Auctions -- Minimizing Average Completion of Dedicated Tasks and Interval Graphs -- A Greedy Facility Location Algorithm Analyzed Using Dual Fitting -- 0.863-Approximation Algorithm for MAX DICUT -- The Maximum Acyclic Subgraph Problem and Degree-3 Graphs -- Some Approximation Results for the Maximum Agreement Forest Problem -- Contributed Talks of RANDOM -- Near-optimum Universal Graphs for Graphs with Bounded Degrees -- On a Generalized Ruin Problem -- On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation -- Exact Sampling in Machine Scheduling Problems -- On Computing Ad-hoc Selective Families -- L Infinity Embeddings -- On Euclidean Embeddings and Bandwidth Minimization -- The Non-approximability of Non-Boolean Predicates -- On the Derandomization of Constant Depth Circuits -- Testing Parenthesis Languages -- Proclaiming Dictators and Juntas or Testing Boolean Formulae -- Equitable Coloring Extends Chernoff-Hoeffding Bounds. |
Record Nr. | UNINA-9910143591803321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2001 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques [[electronic resource] ] : 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeto, NY, USA, August 24-26,2003 / / edited by Sanjeev Arora, Klaus Jansen, Jose D.P. Rolim, Amit Sahai |
Edizione | [1st ed. 2003.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 |
Descrizione fisica | 1 online resource (IX, 411 p.) |
Disciplina | 005.1 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Software engineering
Mathematical optimization Algorithms Numerical analysis Computer science—Mathematics Software Engineering/Programming and Operating Systems Optimization Algorithm Analysis and Problem Complexity Numeric Computing Discrete Mathematics in Computer Science |
ISBN | 3-540-45198-6 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Contributed Talks of APPROX -- Correlation Clustering with Partial Information -- Improved Linear Time Approximation Algorithms for Weighted Matchings -- Covering Graphs Using Trees and Stars -- An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor -- Approximation Algorithms for Channel Allocation Problems in Broadcast Networks -- Asymmetry in k-Center Variants -- An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times -- On the Complexity of Approximating k-Dimensional Matching -- Approximating Market Equilibria -- Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem -- On the Hardness of Approximate Multivariate Integration -- A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem -- Approximating Rooted Connectivity Augmentation Problems -- Effective Routing and Scheduling in Adversarial Queueing Networks -- Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement -- An Improved Algorithm for Approximating the Radii of Point Sets -- Contributed Talks of RANDOM -- Testing Low-Degree Polynomials over GF(2) -- Computational Analogues of Entropy -- Bounds on 2-Query Codeword Testing -- The Lovász Number of Random Graphs -- Perfectly Balanced Allocation -- On Extracting Private Randomness over a Public Channel -- High Degree Vertices and Eigenvalues in the Preferential Attachment Graph -- The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems -- Continuous-Time Quantum Walks on the Symmetric Group -- Distribution-Free Property Testing -- On the Graph-Density of Random 0/1-Polytopes -- A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding -- Tight Bounds for Testing Bipartiteness in General Graphs -- Discrete Quantum Walks Hit Exponentially Faster -- Approximate Testing of Visual Properties -- Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances -- A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries. |
Record Nr. | UNISA-996465960103316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques : 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeto, NY, USA, August 24-26,2003 / / edited by Sanjeev Arora, Klaus Jansen, Jose D.P. Rolim, Amit Sahai |
Edizione | [1st ed. 2003.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 |
Descrizione fisica | 1 online resource (IX, 411 p.) |
Disciplina | 005.1 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Software engineering
Mathematical optimization Algorithms Numerical analysis Computer science—Mathematics Discrete mathematics Software Engineering Optimization Numerical Analysis Discrete Mathematics in Computer Science |
ISBN | 3-540-45198-6 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Contributed Talks of APPROX -- Correlation Clustering with Partial Information -- Improved Linear Time Approximation Algorithms for Weighted Matchings -- Covering Graphs Using Trees and Stars -- An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor -- Approximation Algorithms for Channel Allocation Problems in Broadcast Networks -- Asymmetry in k-Center Variants -- An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times -- On the Complexity of Approximating k-Dimensional Matching -- Approximating Market Equilibria -- Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem -- On the Hardness of Approximate Multivariate Integration -- A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem -- Approximating Rooted Connectivity Augmentation Problems -- Effective Routing and Scheduling in Adversarial Queueing Networks -- Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement -- An Improved Algorithm for Approximating the Radii of Point Sets -- Contributed Talks of RANDOM -- Testing Low-Degree Polynomials over GF(2) -- Computational Analogues of Entropy -- Bounds on 2-Query Codeword Testing -- The Lovász Number of Random Graphs -- Perfectly Balanced Allocation -- On Extracting Private Randomness over a Public Channel -- High Degree Vertices and Eigenvalues in the Preferential Attachment Graph -- The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems -- Continuous-Time Quantum Walks on the Symmetric Group -- Distribution-Free Property Testing -- On the Graph-Density of Random 0/1-Polytopes -- A Gambling Game Arising in the Analysis of Adaptive Randomized Rounding -- Tight Bounds for Testing Bipartiteness in General Graphs -- Discrete Quantum Walks Hit Exponentially Faster -- Approximate Testing of Visual Properties -- Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances -- A Nearly Linear Size 4-Min-Wise Independent Permutation Family by Finite Geometries. |
Record Nr. | UNINA-9910144026203321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Automata, Languages and Programming [[electronic resource] ] : 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000 Proceedings / / edited by Ugo Montanari, Jose D.P. Rolim, Emo Welzl |
Edizione | [1st ed. 2000.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2000 |
Descrizione fisica | 1 online resource (XVI, 952 p.) |
Disciplina | 511.3 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computers
Software engineering Computer communication systems Special purpose computers Computer science—Mathematics Theory of Computation Software Engineering/Programming and Operating Systems Computer Communication Networks Special Purpose and Application-Based Systems Mathematics of Computing |
ISBN | 3-540-45022-X |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talk -- Game Semantics: Achievements and Prospects -- Clique Is Hard to Approximate within n 1-o(1) -- Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time -- Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming -- A Statically Allocated Parallel Functional Language -- An Optimal Minimum Spanning Tree Algorithm -- Improved Shortest Paths on the Word RAM -- Improved Algorithms for Finding Level Ancestors in Dynamic Trees -- Lax Logical Relations -- Reasoning about Idealized ALGOL Using Regular Languages -- The Measurement Process in Domain Theory -- Invited Talk -- Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution -- Monotone Proofs of the Pigeon Hole Principle -- Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models -- Algebraic Models for Contextual Nets -- Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems -- Measures of Nondeterminism in Finite Automata -- LTL Is Expressively Complete for Mazurkiewicz Traces -- An Automata-Theoretic Completeness Proof for Interval Temporal Logic -- Invited Talk -- Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? -- Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search -- Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices -- Variable Independence, Quantifier Elimination, and Constraint Representations -- Constraint Satisfaction Problems and Finite Algebras -- An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing -- Resource Augmentation for Online Bounded Space Bin Packing -- Optimal Projective Algorithms for the List Update Problem -- Efficient Verification Algorithms for One-Counter Processes -- On the Complexity of Bisimulation Problems for Basic Parallel Processes -- Decidable First-Order Transition Logics for PA-Processes -- Invited Talk -- Non Interference for the Analysis of Cryptographic Protocols -- Average Bit-Complexity of Euclidean Algorithms -- Planar Maps and Airy Phenomena -- Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System -- Information Flow vs. Resource Access in the Asynchronous Pi-Calculus (Extended Abstract) -- Award Talk -- The Genomics Revolution and Its Challenges for Algorithmic Research -- Invited Talk -- Alternating the Temporal Picture for Safety -- Necessary and Sufficient Assumptions for Non-interactive Zero-Knowledge Proofs of Knowledge for All NP Relations -- Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP -- A New Unfolding Approach to LTL Model Checking -- Reasoning about Message Passing in Finite State Environments -- Extended Notions of Security for Multicast Public Key Cryptosystems -- One-Round Secure Computation and Secure Autonomous Mobile Agents -- Round-Optimal and Abuse-Free Optimistic Multi-party Contract Signing -- On the Centralizer of a Finite Set -- On the Power of Tree-Walking Automata -- Determinization of Transducers over Infinite Words -- Invited Talk -- Constraint Programming and Graph Algorithms -- Scalable Secure Storage when Half the System Is Faulty -- Generating Partial and Multiple Transversals of a Hypergraph -- Revisiting the Correspondence between Cut Elimination and Normalisation -- Negation Elimination from Simple Equational Formulae -- Hardness of Set Cover with Intersection 1 -- Strong Inapproximability of the Basic k-Spanner Problem -- Infinite Series-Parallel Posets: Logic and Languages -- On Deciding if Deterministic Rabin Language Is in Büchi Class -- On Message Sequence Graphs and Finitely Generated Regular MSC Languages -- Invited Talk -- Pseudorandomness -- A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols -- Deterministic Radio Broadcasting -- An ?-Complete Equational Specification of Interleaving -- A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors -- Tight Size Bounds for Packet Headers in Narrow Meshes -- Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link -- On the Logical Characterisation of Performability Properties -- On the Representation of Timed Polyhedra -- Invited Talk -- Min-wise Independent Permutations: Theory and Practice -- Testing Acyclicity of Directed Graphs in Sublinear Time -- Computing the Girth of a Planar Graph -- Lower Bounds Are Not Easier over the Reals: Inside PH -- Unlearning Helps -- Fast Approximation Schemes for Euclidean Multi-connectivity Problems -- Approximate TSP in Graphs with Forbidden Minors -- Polynomial Time Approximation Schemes for General Multiprocessor Job Shop Scheduling -- The Many Faces of a Translation -- Gales and the Constructive Dimension of Individual Sequences -- The Global Power of Additional Queries to p-Random Oracles -- Homogenization and the Polynomial Calculus. |
Record Nr. | UNISA-996465376503316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2000 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Automata, Languages and Programming : 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000 Proceedings / / edited by Ugo Montanari, Jose D.P. Rolim, Emo Welzl |
Edizione | [1st ed. 2000.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2000 |
Descrizione fisica | 1 online resource (XVI, 952 p.) |
Disciplina | 511.3 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computers
Software engineering Computer communication systems Special purpose computers Computer science—Mathematics Theory of Computation Software Engineering/Programming and Operating Systems Computer Communication Networks Special Purpose and Application-Based Systems Mathematics of Computing |
ISBN | 3-540-45022-X |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talk -- Game Semantics: Achievements and Prospects -- Clique Is Hard to Approximate within n 1-o(1) -- Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time -- Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming -- A Statically Allocated Parallel Functional Language -- An Optimal Minimum Spanning Tree Algorithm -- Improved Shortest Paths on the Word RAM -- Improved Algorithms for Finding Level Ancestors in Dynamic Trees -- Lax Logical Relations -- Reasoning about Idealized ALGOL Using Regular Languages -- The Measurement Process in Domain Theory -- Invited Talk -- Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution -- Monotone Proofs of the Pigeon Hole Principle -- Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models -- Algebraic Models for Contextual Nets -- Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems -- Measures of Nondeterminism in Finite Automata -- LTL Is Expressively Complete for Mazurkiewicz Traces -- An Automata-Theoretic Completeness Proof for Interval Temporal Logic -- Invited Talk -- Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? -- Deterministic Algorithms for k-SAT Based on Covering Codes and Local Search -- Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices -- Variable Independence, Quantifier Elimination, and Constraint Representations -- Constraint Satisfaction Problems and Finite Algebras -- An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing -- Resource Augmentation for Online Bounded Space Bin Packing -- Optimal Projective Algorithms for the List Update Problem -- Efficient Verification Algorithms for One-Counter Processes -- On the Complexity of Bisimulation Problems for Basic Parallel Processes -- Decidable First-Order Transition Logics for PA-Processes -- Invited Talk -- Non Interference for the Analysis of Cryptographic Protocols -- Average Bit-Complexity of Euclidean Algorithms -- Planar Maps and Airy Phenomena -- Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System -- Information Flow vs. Resource Access in the Asynchronous Pi-Calculus (Extended Abstract) -- Award Talk -- The Genomics Revolution and Its Challenges for Algorithmic Research -- Invited Talk -- Alternating the Temporal Picture for Safety -- Necessary and Sufficient Assumptions for Non-interactive Zero-Knowledge Proofs of Knowledge for All NP Relations -- Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP -- A New Unfolding Approach to LTL Model Checking -- Reasoning about Message Passing in Finite State Environments -- Extended Notions of Security for Multicast Public Key Cryptosystems -- One-Round Secure Computation and Secure Autonomous Mobile Agents -- Round-Optimal and Abuse-Free Optimistic Multi-party Contract Signing -- On the Centralizer of a Finite Set -- On the Power of Tree-Walking Automata -- Determinization of Transducers over Infinite Words -- Invited Talk -- Constraint Programming and Graph Algorithms -- Scalable Secure Storage when Half the System Is Faulty -- Generating Partial and Multiple Transversals of a Hypergraph -- Revisiting the Correspondence between Cut Elimination and Normalisation -- Negation Elimination from Simple Equational Formulae -- Hardness of Set Cover with Intersection 1 -- Strong Inapproximability of the Basic k-Spanner Problem -- Infinite Series-Parallel Posets: Logic and Languages -- On Deciding if Deterministic Rabin Language Is in Büchi Class -- On Message Sequence Graphs and Finitely Generated Regular MSC Languages -- Invited Talk -- Pseudorandomness -- A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols -- Deterministic Radio Broadcasting -- An ?-Complete Equational Specification of Interleaving -- A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors -- Tight Size Bounds for Packet Headers in Narrow Meshes -- Wavelength Assignment Problem on All-Optical Networks with k Fibres per Link -- On the Logical Characterisation of Performability Properties -- On the Representation of Timed Polyhedra -- Invited Talk -- Min-wise Independent Permutations: Theory and Practice -- Testing Acyclicity of Directed Graphs in Sublinear Time -- Computing the Girth of a Planar Graph -- Lower Bounds Are Not Easier over the Reals: Inside PH -- Unlearning Helps -- Fast Approximation Schemes for Euclidean Multi-connectivity Problems -- Approximate TSP in Graphs with Forbidden Minors -- Polynomial Time Approximation Schemes for General Multiprocessor Job Shop Scheduling -- The Many Faces of a Translation -- Gales and the Constructive Dimension of Individual Sequences -- The Global Power of Additional Queries to p-Random Oracles -- Homogenization and the Polynomial Calculus. |
Record Nr. | UNINA-9910767551103321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2000 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Randomization and Approximation Techniques in Computer Science [[electronic resource] ] : 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings / / edited by Jose D.P. Rolim, Salil Vadhan |
Edizione | [1st ed. 2002.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002 |
Descrizione fisica | 1 online resource (VIII, 284 p.) |
Disciplina | 004/.07/27 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computer programming
Computer science—Mathematics Algorithms Numerical analysis Programming Techniques Mathematics of Computing Algorithm Analysis and Problem Complexity Numeric Computing Discrete Mathematics in Computer Science |
ISBN | 3-540-45726-7 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Counting Distinct Elements in a Data Stream -- On Testing Convexity and Submodularity -- ?-Regular Languages Are Testable with a Constant Number of Queries -- Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes -- Counting and Sampling H-Colourings -- Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs -- On the 2-Colorability of Random Hypergraphs -- Percolation on Finite Cayley Graphs -- Computing Graph Properties by Randomized Subcube Partitions -- Bisection of Random Cubic Graphs -- Small k-Dominating Sets of Regular Graphs -- Finding Sparse Induced Subgraphs of Semirandom Graphs -- Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View -- Quantum Walks on the Hypercube -- Randomness-Optimal Characterization of Two NP Proof Systems -- A Probabilistic-Time Hierarchy Theorem for “Slightly Non-uniform” Algorithms -- Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good -- Is Constraint Satisfaction Over Two Variables Always Easy? -- Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications -- On the Eigenvalue Power Law -- Classifying Special Interest Groups in Web Graphs. |
Record Nr. | UNISA-996465570103316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Randomization and Approximation Techniques in Computer Science : 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings / / edited by Jose D.P. Rolim, Salil Vadhan |
Edizione | [1st ed. 2002.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002 |
Descrizione fisica | 1 online resource (VIII, 284 p.) |
Disciplina | 004/.07/27 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computer programming
Computer science—Mathematics Algorithms Numerical analysis Programming Techniques Mathematics of Computing Algorithm Analysis and Problem Complexity Numeric Computing Discrete Mathematics in Computer Science |
ISBN | 3-540-45726-7 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Counting Distinct Elements in a Data Stream -- On Testing Convexity and Submodularity -- ?-Regular Languages Are Testable with a Constant Number of Queries -- Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes -- Counting and Sampling H-Colourings -- Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs -- On the 2-Colorability of Random Hypergraphs -- Percolation on Finite Cayley Graphs -- Computing Graph Properties by Randomized Subcube Partitions -- Bisection of Random Cubic Graphs -- Small k-Dominating Sets of Regular Graphs -- Finding Sparse Induced Subgraphs of Semirandom Graphs -- Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View -- Quantum Walks on the Hypercube -- Randomness-Optimal Characterization of Two NP Proof Systems -- A Probabilistic-Time Hierarchy Theorem for “Slightly Non-uniform” Algorithms -- Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good -- Is Constraint Satisfaction Over Two Variables Always Easy? -- Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications -- On the Eigenvalue Power Law -- Classifying Special Interest Groups in Web Graphs. |
Record Nr. | UNINA-9910143898803321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2002 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|