Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Approximation, randomization and combinatorial optimization : algorithms and techniques : 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006, and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30, 2006 : proceedings / / Josep Diaz ... [et al.] (eds.)
| Approximation, randomization and combinatorial optimization : algorithms and techniques : 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006, and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30, 2006 : proceedings / / Josep Diaz ... [et al.] (eds.) |
| Edizione | [1st ed. 2006.] |
| Pubbl/distr/stampa | Berlin, : Springer, 2006 |
| Descrizione fisica | 1 online resource (XII, 522 p.) |
| Disciplina | 005.1 |
| Altri autori (Persone) | DiazJ <1950-> (Josep) |
| Collana |
Lecture notes in computer science
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
| Soggetto topico |
Computer science - Statistical methods
Computer algorithms |
| ISBN | 3-540-38045-0 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Talks -- On Nontrivial Approximation of CSPs -- Analysis of Algorithms on the Cores of Random Graphs -- Contributed Talks of APPROX -- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs -- Approximating Precedence-Constrained Single Machine Scheduling by Coloring -- Minimizing Setup and Beam-On Times in Radiation Therapy -- On the Value of Preemption in Scheduling -- An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs -- Tight Results on Minimum Entropy Set Cover -- A Tight Lower Bound for the Steiner Point Removal Problem on Trees -- Single-Source Stochastic Routing -- An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem -- Online Algorithms to Minimize Resource Reallocations and Network Communication -- Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs -- Combinatorial Algorithms for Data Migration to Minimize Average Completion Time -- LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times -- Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees -- Improved Algorithms for Data Migration -- Approximation Algorithms for Graph Homomorphism Problems -- Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem -- Hardness of Preemptive Finite Capacity Dial-a-Ride -- Minimum Vehicle Routing with a Common Deadline -- Stochastic Combinatorial Optimization with Controllable Risk Aversion Level -- Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems -- Better Approximations for the Minimum Common Integer Partition Problem -- Contributed Talks of RANDOM -- On Pseudorandom Generators with Linear Stretch in NC0 -- A Fast Random Sampling Algorithm for Sparsifying Matrices -- The Effect of Boundary Conditions on Mixing Rates of Markov Chains -- Adaptive Sampling and Fast Low-Rank Matrix Approximation -- Robust Local Testability of Tensor Products of LDPC Codes -- Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods -- Dobrushin Conditions and Systematic Scan -- Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems -- Robust Mixing -- Approximating Average Parameters of Graphs -- Local Decoding and Testing for Homomorphisms -- Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy -- Randomness-Efficient Sampling Within NC 1 -- Monotone Circuits for the Majority Function -- Space Complexity vs. Query Complexity -- Consistency of Local Density Matrices Is QMA-Complete -- On Bounded Distance Decoding for General Lattices -- Threshold Functions for Asymmetric Ramsey Properties Involving Cliques -- Distance Approximation in Bounded-Degree and General Sparse Graphs -- Fractional Matching Via Balls-and-Bins -- A Randomized Solver for Linear Systems with Exponential Convergence -- Maintaining External Memory Efficient Hash Tables. |
| Altri titoli varianti |
9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems
Ninth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2006 10th International Workshop on Randomization and Computation Tenth International Workshop on Randomization and Computation RANDOM 2006 |
| Record Nr. | UNINA-9910484212003321 |
| Berlin, : Springer, 2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Approximation, randomization, and combinatorial optimization : algorithms and techniques ; 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010 ; proceedings / / Maria Serna ... [et al.] (eds.)
| Approximation, randomization, and combinatorial optimization : algorithms and techniques ; 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010 ; proceedings / / Maria Serna ... [et al.] (eds.) |
| Edizione | [1st ed. 2010.] |
| Pubbl/distr/stampa | Berlin ; ; New York, : Springer, c2010 |
| Descrizione fisica | 1 online resource (XIII, 782 p. 54 illus.) |
| Disciplina | 005.1 |
| Altri autori (Persone) | SernaMaria <1959-> |
| Collana |
Lecture notes in computer science
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
| Soggetto topico |
Computer algorithms
Computer science - Statistical methods |
| ISBN |
1-280-38852-8
9786613566447 3-642-15369-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Contributed Talks of APPROX -- Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem -- Improved Inapproximability for Submodular Maximization -- Approximation Algorithms for the Directed k-Tour and k-Stroll Problems -- Submodular Secretary Problem and Extensions -- Approximation Algorithms for Min-Max Generalization Problems -- Min-Power Strong Connectivity -- The Complexity of Approximately Counting Stable Matchings -- Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs -- Approximating Linear Threshold Predicates -- Approximating Sparsest Cut in Graphs of Bounded Treewidth -- On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors -- Vertex Sparsifiers: New Results from Old Techniques -- PTAS for Weighted Set Cover on Unit Squares -- Improved Lower Bounds for the Universal and a priori TSP -- Proximity Algorithms for Nearly-Doubling Spaces -- Matrix Sparsification and the Sparse Null Space Problem -- The Checkpoint Problem -- The Euclidean Distortion of Flat Tori -- Online Embeddings -- Approximation Algorithms for Intersection Graphs -- An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs -- Improved Algorithm for the Half-Disjoint Paths Problem -- Approximate Lasserre Integrality Gap for Unique Games -- Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses -- Maximum Flows on Disjoint Paths -- Approximation Algorithms for Reliable Stochastic Combinatorial Optimization -- How to Schedule When You Have to Buy Your Energy -- Improving Integrality Gaps via Chvátal-Gomory Rounding -- Contributed Talks of RANDOM -- Uniform Derandomization from Pathetic Lower Bounds -- Testing Boolean Function Isomorphism -- Better Size Estimation for Sparse Matrix Products -- Low Rate Is Insufficient for Local Testability -- Reconstruction Threshold for the Hardcore Model -- Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners -- Monotonicity Testing and Shortest-Path Routing on the Cube -- Better Gap-Hamming Lower Bounds via Better Round Elimination -- Propagation Connectivity of Random Hypergraphs -- Improved Pseudorandom Generators for Depth 2 Circuits -- The Structure of Winning Strategies in Parallel Repetition Games -- Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries -- Periodicity in Streams -- Rumor Spreading on Random Regular Graphs and Expanders -- On Testing Computability by Small Width OBDDs -- Learning and Lower Bounds for AC 0 with Threshold Gates -- Liftings of Tree-Structured Markov Chains -- Constructive Proofs of Concentration Bounds -- Almost-Euclidean Subspaces of via Tensor Products: A Simple Approach to Randomness Reduction -- Testing Outerplanarity of Bounded Degree Graphs -- Two-Source Extractors Secure against Quantum Adversaries -- Locally Testable vs. Locally Decodable Codes -- Differential Privacy and the Fat-Shattering Dimension of Linear Queries -- Two Theorems on List Decoding -- Delaying Satisfiability for Random 2SAT -- Improved Rounding for Parallel Repeated Unique Games -- A Query Efficient Non-adaptive Long Code Test with Perfect Completeness -- Relativized Worlds without Worst-Case to Average-Case Reductions for NP -- A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. |
| Altri titoli varianti |
APPROX 2010
RANDOM 2010 |
| Record Nr. | UNINA-9910484749503321 |
| Berlin ; ; New York, : Springer, c2010 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Approximation, randomization, and combinatorial optimization : algorithms and techniques : 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August, 21-23, 2009 : proceedings / / Irit Dinur ... [et al.] (eds.)
| Approximation, randomization, and combinatorial optimization : algorithms and techniques : 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August, 21-23, 2009 : proceedings / / Irit Dinur ... [et al.] (eds.) |
| Edizione | [1st ed. 2009.] |
| Pubbl/distr/stampa | Berlin ; ; New York, : Springer, c2009 |
| Descrizione fisica | 1 online resource (XII, 742 p. 41 illus.) |
| Disciplina | 005.11 |
| Altri autori (Persone) | DinurIrit |
| Collana | Lecture notes in computer science |
| Soggetto topico |
Computer algorithms
Computer science - Statistical methods |
| ISBN | 3-642-03685-6 |
| Classificazione |
DAT 517f
DAT 537f MAT 410f MAT 913f SS 4800 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Contributed Talks of APPROX -- Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs -- Adaptive Sampling for k-Means Clustering -- Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs -- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs -- Truthful Mechanisms via Greedy Iterative Packing -- Resource Minimization Job Scheduling -- The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders -- New Hardness Results for Diophantine Approximation -- PASS Approximation -- Optimal Sherali-Adams Gaps from Pairwise Independence -- An Approximation Scheme for Terrain Guarding -- Scheduling with Outliers -- Improved Inapproximability Results for Maximum k-Colorable Subgraph -- Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems -- On the Optimality of Gluing over Scales -- On Hardness of Pricing Items for Single-Minded Bidders -- Real-Time Message Routing and Scheduling -- Approximating Some Network Design Problems with Node Costs -- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties -- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy -- Minimizing Average Shortest Path Distances via Shortcut Edge Addition -- Approximating Node-Connectivity Augmentation Problems -- A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem -- Approximation Algorithms for Domatic Partitions of Unit Disk Graphs -- On the Complexity of the Asymmetric VPN Problem -- Contributed Talks of RANDOM -- Deterministic Approximation Algorithms for the Nearest Codeword Problem -- Strong Parallel Repetition Theorem for Free Projection Games -- Random Low Degree Polynomials are Hard to Approximate -- Composition of Semi-LTCs by Two-Wise Tensor Products -- On the Security of Goldreich’s One-Way Function -- Random Tensors and Planted Cliques -- Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry -- Average-Case Analyses of Vickrey Costs -- A Hypergraph Dictatorship Test with Perfect Completeness -- Extractors Using Hardness Amplification -- How Well Do Random Walks Parallelize? -- An Analysis of Random-Walk Cuckoo Hashing -- Hierarchy Theorems for Property Testing -- Algorithmic Aspects of Property Testing in the Dense Graphs Model -- Succinct Representation of Codes with Applications to Testing -- Efficient Quantum Tensor Product Expanders and k-Designs -- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND -- Pseudorandom Generators and Typically-Correct Derandomization -- Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions -- Tolerant Linearity Testing and Locally Testable Codes -- Pseudorandom Bit Generators That Fool Modular Sums -- The Glauber Dynamics for Colourings of Bounded Degree Trees -- Testing ±1-weight halfspace -- Small-Bias Spaces for Group Products -- Small Clique Detection and Approximate Nash Equilibria -- Testing Computability by Width Two OBDDs -- Improved Polynomial Identity Testing for Read-Once Formulas -- Smooth Analysis of the Condition Number and the Least Singular Value. |
| Altri titoli varianti |
APPROX 2009
RANDOM 2009 |
| Record Nr. | UNINA-9910484414603321 |
| Berlin ; ; New York, : Springer, c2009 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Approximation, randomization, and combinatorial optimization : algorithms and techniques : 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005, and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005 : proceedings / / Chandra Chekuri ... [et al.] (eds.)
| Approximation, randomization, and combinatorial optimization : algorithms and techniques : 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005, and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005 : proceedings / / Chandra Chekuri ... [et al.] (eds.) |
| Edizione | [1st ed. 2005.] |
| Pubbl/distr/stampa | Berlin, : Springer, 2005 |
| Descrizione fisica | 1 online resource (XI, 495 p.) |
| Disciplina | 005.1 |
| Altri autori (Persone) | ChekuriChandra |
| Collana | Lecture notes in computer science |
| Soggetto topico |
Computer science - Statistical methods
Computer algorithms |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Contributed Talks of APPROX -- The Network as a Storage Device: Dynamic Routing with Bounded Buffers -- Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT -- What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs -- A Rounding Algorithm for Approximating Minimum Manhattan Networks -- Packing Element-Disjoint Steiner Trees -- Approximating the Bandwidth of Caterpillars -- Where’s the Winner? Max-Finding and Sorting with Metric Costs -- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization -- The Complexity of Making Unique Choices: Approximating 1-in-k SAT -- Approximating the Distortion -- Approximating the Best-Fit Tree Under L p Norms -- Beating a Random Assignment -- Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints -- Approximation Algorithms for Network Design and Facility Location with Service Capacities -- Finding Graph Matchings in Data Streams -- A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses -- Efficient Approximation of Convex Recolorings -- Approximation Algorithms for Requirement Cut on Graphs -- Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems -- Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy -- Contributed Talks of RANDOM -- Bounds for Error Reduction with Few Quantum Queries -- Sampling Bounds for Stochastic Optimization -- An Improved Analysis of Mergers -- Finding a Maximum Independent Set in a Sparse Random Graph -- On the Error Parameter of Dispersers -- Tolerant Locally Testable Codes -- A Lower Bound on List Size for List Decoding -- A Lower Bound for Distribution-Free Monotonicity Testing -- On Learning Random DNF Formulas Under the Uniform Distribution -- Derandomized Constructions of k-Wise (Almost) Independent Permutations -- Testing Periodicity -- The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem -- The Online Clique Avoidance Game on Random Graphs -- A Generating Function Method for the Average-Case Analysis of DPLL -- A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas -- Mixing Points on a Circle -- Derandomized Squaring of Graphs -- Tight Bounds for String Reconstruction Using Substring Queries -- Reconstructive Dispersers and Hitting Set Generators -- The Tensor Product of Two Codes Is Not Necessarily Robustly Testable -- Fractional Decompositions of Dense Hypergraphs. |
| Altri titoli varianti |
APPROX 2005
RANDOM 2005 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems Eighth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems International Workshop on Approximation Algorithms for Combinatorial Optimization Problems 9th International Workshop on Randomization and Computation Ninth International Workshop on Randomization and Computation International Workshop on Randomization and Computation |
| Record Nr. | UNINA-9910483161103321 |
| Berlin, : Springer, 2005 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Pairwise independence and derandomization / Michael Luby, Avi Wigderson
| Pairwise independence and derandomization / Michael Luby, Avi Wigderson |
| Autore | Luby, Michael |
| Pubbl/distr/stampa | Boston ; Delft : Now, c2006 |
| Descrizione fisica | ix, 67 p. ; 24 cm |
| Disciplina | 004.151 |
| Altri autori (Persone) | Wigderson, Aviauthor |
| Collana | Foundations and trends in theoretical computer science ; 1, n. 4 (2005) |
| Soggetto topico |
Computer science - Mathematics
Computer science - Statistical methods Computational complexity Numbers, Random |
| ISBN | 1933019220 |
| Classificazione |
AMS 68W20
LC QA76.9.M35L83 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Record Nr. | UNISALENTO-991002460969707536 |
Luby, Michael
|
||
| Boston ; Delft : Now, c2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. del Salento | ||
| ||
Randomization and approximation techniques in computer science : second international workshop RANDOM '98, Barcelona, Spain, October 8-10, 1998 : proceedings / / Michael Luby, JoseÌ Rolim, Maria Serna (editors)
| Randomization and approximation techniques in computer science : second international workshop RANDOM '98, Barcelona, Spain, October 8-10, 1998 : proceedings / / Michael Luby, JoseÌ Rolim, Maria Serna (editors) |
| Edizione | [1st ed. 1998.] |
| Pubbl/distr/stampa | Berlin ; ; Heidelberg : , : Springer, , [1998] |
| Descrizione fisica | 1 online resource (IX, 385 p.) |
| Disciplina | 004.015114 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico | Computer science - Statistical methods |
| ISBN | 3-540-49543-6 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Paper -- Disjoint Paths in Expander Graphs via Random Walks: a Short Survey -- Regular Papers -- A Derandomization Using Min-Wise Independent Permutations -- An Algorithmic Embedding of Graphs via Perfect Matchings -- Deterministic Hypergraph Coloring and Its Applications -- On the Derandomization of Space-Bounded Computations -- Talagrand’s Inequality and Locality in Distributed Computing -- On-line Bin-Stretching -- Combinatorial Linear Programming: Geometry Can Help -- A Note on Bounding the Mixing Time by Linear Programming -- Robotic Exploration, Brownian Motion and Electrical Resistance -- Fringe analysis of synchronized parallel algorithms on 2–3 trees -- On Balls and Bins with Deletions -- “Balls into Bins” — A Simple and Tight Analysis -- Invited Paper -- Tornado Codes: Practical Erasure Codes Based on Random Irregular Graphs -- Regular Papers -- Using Approximation Hardness to Achieve Dependable Computation -- Complexity of Sequential Pattern Matching Algorithms -- A Random Server Model for Private Information Retrieval -- Almost Optimal (on the average) Combinatorial Algorithms for Boolean Matrix Product Witnesses, Computing the Diameter (Extended Abstract) -- Randomized Lower Bounds for Online Path Coloring -- Parallel Random Search and Tabu Search for the Minimal Consistent Subset Selection Problem -- On Various Cooling Schedules for Simulated Annealing Applied to the Job Shop Problem -- A High Performance Approximate Algorithm for the Steiner Problem in Graphs -- Invited Paper -- Random Geometric Problems on [0, 1]2 -- Regular Papers -- A Role of Constraint in Self-Organization -- Constructive Bounds and Exact Expectations for the Random Assignment Problem -- The “Burnside Process” Converges Slowly -- Quicksort Again Revisited -- Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems -- Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow. |
| Record Nr. | UNINA-9910143468603321 |
| Berlin ; ; Heidelberg : , : Springer, , [1998] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Randomization and approximation techniques in computer science : second international workshop RANDOM '98, Barcelona, Spain, October 8-10, 1998 : proceedings / / Michael Luby, JoseÌ Rolim, Maria Serna (editors)
| Randomization and approximation techniques in computer science : second international workshop RANDOM '98, Barcelona, Spain, October 8-10, 1998 : proceedings / / Michael Luby, JoseÌ Rolim, Maria Serna (editors) |
| Edizione | [1st ed. 1998.] |
| Pubbl/distr/stampa | Berlin ; ; Heidelberg : , : Springer, , [1998] |
| Descrizione fisica | 1 online resource (IX, 385 p.) |
| Disciplina | 004.015114 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico | Computer science - Statistical methods |
| ISBN | 3-540-49543-6 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Paper -- Disjoint Paths in Expander Graphs via Random Walks: a Short Survey -- Regular Papers -- A Derandomization Using Min-Wise Independent Permutations -- An Algorithmic Embedding of Graphs via Perfect Matchings -- Deterministic Hypergraph Coloring and Its Applications -- On the Derandomization of Space-Bounded Computations -- Talagrand’s Inequality and Locality in Distributed Computing -- On-line Bin-Stretching -- Combinatorial Linear Programming: Geometry Can Help -- A Note on Bounding the Mixing Time by Linear Programming -- Robotic Exploration, Brownian Motion and Electrical Resistance -- Fringe analysis of synchronized parallel algorithms on 2–3 trees -- On Balls and Bins with Deletions -- “Balls into Bins” — A Simple and Tight Analysis -- Invited Paper -- Tornado Codes: Practical Erasure Codes Based on Random Irregular Graphs -- Regular Papers -- Using Approximation Hardness to Achieve Dependable Computation -- Complexity of Sequential Pattern Matching Algorithms -- A Random Server Model for Private Information Retrieval -- Almost Optimal (on the average) Combinatorial Algorithms for Boolean Matrix Product Witnesses, Computing the Diameter (Extended Abstract) -- Randomized Lower Bounds for Online Path Coloring -- Parallel Random Search and Tabu Search for the Minimal Consistent Subset Selection Problem -- On Various Cooling Schedules for Simulated Annealing Applied to the Job Shop Problem -- A High Performance Approximate Algorithm for the Steiner Problem in Graphs -- Invited Paper -- Random Geometric Problems on [0, 1]2 -- Regular Papers -- A Role of Constraint in Self-Organization -- Constructive Bounds and Exact Expectations for the Random Assignment Problem -- The “Burnside Process” Converges Slowly -- Quicksort Again Revisited -- Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems -- Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow. |
| Record Nr. | UNISA-996466108203316 |
| Berlin ; ; Heidelberg : , : Springer, , [1998] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Randomization, approximation and combinatorial optimization : algorithms and techniques : Third International Workshop on Randomization and approximation Techniques in Computer Science and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX '99 Berkeley, USA, August 8-11, 1999 : proceedings / / Dorit Hochbaum [and three others], editors
| Randomization, approximation and combinatorial optimization : algorithms and techniques : Third International Workshop on Randomization and approximation Techniques in Computer Science and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX '99 Berkeley, USA, August 8-11, 1999 : proceedings / / Dorit Hochbaum [and three others], editors |
| Edizione | [1st ed. 1999.] |
| Pubbl/distr/stampa | Berlin ; ; Heidelberg : , : Springer, , [1999] |
| Descrizione fisica | 1 online resource (X, 298 p.) |
| Disciplina | 004.015113 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Computer science
Computer science - Statistical methods |
| ISBN | 3-540-48413-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Session Random 1 -- Completeness and Robustness Properties of Min-Wise Independent Permutations -- Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families -- Session Approx 1 -- Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths -- Approximating Minimum Manhattan Networks -- Approximation of Multi-Color Discrepancy -- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem -- Session Approx 2 -- Set Cover with Requirements and Costs Evolving over Time -- Multicoloring Planar Graphs and Partial k-Trees -- Session: Random 2 -- Testing the Diameter of Graphs -- Improved Testing Algorithms for Monotonicity -- Linear Consistency Testing -- Improved Bounds for Sampling Contingency Tables -- Invited Talk -- Probabilistic and Deterministic Approximations of the Permanent -- Session Random 3 -- Improved Derandomization of BPP Using a Hitting Set Generator -- Probabilistic Construction of Small Strongly Sum-Free Sets via Large Sidon Sets -- Session Approx 3 -- Stochastic Machine Scheduling: Performance Guarantees for LP-Based Priority Policies -- Efficient Redundant Assignments under Fault-Tolerance Constraints -- Scheduling with Machine Cost -- A Linear Time Approximation Scheme for the Job Shop Scheduling Problem -- Invited Talk -- Randomized Rounding for Semidefinite Programs – Variations on the MAX CUT Example -- Session Approx 4 -- Hardness Results for the Power Range Assignment Problem in Packet Radio Networks -- A New Approximation Algorithm for the Demand Routing and Slotting Problem with Unit Demands on Rings -- Session Random 4 -- Algorithms for Graph Partitioning on the Planted Partition Model -- A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest -- Fast Approximate PCPs for Multidimensional Bin-Packing Problems -- Pfaffian Algorithms for Sampling Routings on Regions with Free Boundary Conditions -- Minisymposium on Scheduling Talks -- Scheduling with Unexpected Machine Breakdowns -- Scheduling on a Constant Number of Machines. |
| Record Nr. | UNISA-996465598103316 |
| Berlin ; ; Heidelberg : , : Springer, , [1999] | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
