Approximation and Online Algorithms [[electronic resource] ] : 5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007, Revised Papers / / edited by Christos Kaklamanis, Martin Skutella |
Edizione | [1st ed. 2008.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 |
Descrizione fisica | 1 online resource (X, 294 p.) |
Disciplina | 519 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Software engineering
Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Software Engineering Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
ISBN | 3-540-77918-3 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations -- Improved Lower Bounds for Non-utilitarian Truthfulness -- Buyer-Supplier Games: Optimization over the Core -- Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines -- A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum Delays -- Online Algorithm for Parallel Job Scheduling and Strip Packing -- Geometric Spanners with Small Chromatic Number -- Approximating Largest Convex Hulls for Imprecise Points -- A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem -- Covering the Edges of Bipartite Graphs Using K 2,2 Graphs -- On Min-Max r-Gatherings -- On the Max Coloring Problem -- Full and Local Information in Distributed Decision Making -- The Minimum Substring Cover Problem -- A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs -- On the Online Unit Clustering Problem -- Better Bounds for Incremental Medians -- Minimum Weighted Sum Bin Packing -- Approximation Schemes for Packing Splittable Items with Cardinality Constraints -- A Randomized Algorithm for Two Servers in Cross Polytope Spaces -- Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems -- Online Rectangle Filling. |
Record Nr. | UNINA-9910483662003321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation and Online Algorithms [[electronic resource] ] : 4th International Workshop, WAOA 2006, Zurich, Switzerland, September 14-15, 2006, Revised Papers / / edited by Thomas Erlebach, Christos Kaklamanis |
Edizione | [1st ed. 2007.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2007 |
Descrizione fisica | 1 online resource (X, 346 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Software engineering
Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Software Engineering Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
ISBN | 3-540-69514-1 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Approximation Algorithms for Scheduling Problems with Exact Delays -- Bidding to the Top: VCG and Equilibria of Position-Based Auctions -- Coping with Interference: From Maximum Coverage to Planning Cellular Networks -- Online Dynamic Programming Speedups -- Covering Many or Few Points with Unit Disks -- On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems -- Online k-Server Routing Problems -- Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem -- Improved Approximation Bounds for Edge Dominating Set in Dense Graphs -- A Randomized Algorithm for Online Unit Clustering -- On Hierarchical Diameter-Clustering, and the Supplier Problem -- Bin Packing with Rejection Revisited -- On Bin Packing with Conflicts -- Approximate Distance Queries in Disk Graphs -- Network Design with Edge-Connectivity and Degree Constraints -- Approximating Maximum Cut with Limited Unbalance -- Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems -- Improved Online Hypercube Packing -- Competitive Online Multicommodity Routing -- The k-Allocation Problem and Its Variants -- An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions -- Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set -- Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search -- Approximation Algorithms for Multi-criteria Traveling Salesman Problems -- The Survival of the Weakest in Networks -- Online Distributed Object Migration. |
Record Nr. | UNISA-996465599003316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2007 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation and Online Algorithms [[electronic resource] ] : 4th International Workshop, WAOA 2006, Zurich, Switzerland, September 14-15, 2006, Revised Papers / / edited by Thomas Erlebach, Christos Kaklamanis |
Edizione | [1st ed. 2007.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2007 |
Descrizione fisica | 1 online resource (X, 346 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Software engineering
Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Software Engineering Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
ISBN | 3-540-69514-1 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Approximation Algorithms for Scheduling Problems with Exact Delays -- Bidding to the Top: VCG and Equilibria of Position-Based Auctions -- Coping with Interference: From Maximum Coverage to Planning Cellular Networks -- Online Dynamic Programming Speedups -- Covering Many or Few Points with Unit Disks -- On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems -- Online k-Server Routing Problems -- Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem -- Improved Approximation Bounds for Edge Dominating Set in Dense Graphs -- A Randomized Algorithm for Online Unit Clustering -- On Hierarchical Diameter-Clustering, and the Supplier Problem -- Bin Packing with Rejection Revisited -- On Bin Packing with Conflicts -- Approximate Distance Queries in Disk Graphs -- Network Design with Edge-Connectivity and Degree Constraints -- Approximating Maximum Cut with Limited Unbalance -- Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems -- Improved Online Hypercube Packing -- Competitive Online Multicommodity Routing -- The k-Allocation Problem and Its Variants -- An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions -- Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set -- Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search -- Approximation Algorithms for Multi-criteria Traveling Salesman Problems -- The Survival of the Weakest in Networks -- Online Distributed Object Migration. |
Record Nr. | UNINA-9910484280403321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2007 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation and Online Algorithms [[electronic resource] ] : Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Selected Papers / / edited by Thomas Erlebach, Giuseppe Persiano |
Edizione | [1st ed. 2006.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 |
Descrizione fisica | 1 online resource (X, 349 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Software engineering
Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Software Engineering Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
ISBN | 3-540-32208-6 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | “Almost Stable” Matchings in the Roommates Problem -- On the Minimum Load Coloring Problem -- Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT -- The Hardness of Network Design for Unsplittable Flow with Selfish Users -- Improved Approximation Algorithm for Convex Recoloring of Trees -- Exploiting Locality: Approximating Sorting Buffers -- Approximate Fair Cost Allocation in Metric Traveling Salesman Games -- Rounding of Sequences and Matrices, with Applications -- A Note on Semi-online Machine Covering -- SONET ADMs Minimization with Divisible Paths -- The Conference Call Search Problem in Wireless Networks -- Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents -- Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost -- A Better-Than-Greedy Algorithm for k-Set Multicover -- Deterministic Online Optical Call Admission Revisited -- Scheduling Parallel Jobs with Linear Speedup -- Online Removable Square Packing -- The Online Target Date Assignment Problem -- Approximation and Complexity of k–Splittable Flows -- On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem -- Tighter Approximations for Maximum Induced Matchings in Regular Graphs -- On Approximating Restricted Cycle Covers -- A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs -- Speed Scaling of Tasks with Precedence Constraints -- Partial Multicuts in Trees -- Approximation Schemes for Packing with Item Fragmentation. |
Record Nr. | UNISA-996466153003316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation and Online Algorithms [[electronic resource] ] : Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Selected Papers / / edited by Thomas Erlebach, Giuseppe Persiano |
Edizione | [1st ed. 2006.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 |
Descrizione fisica | 1 online resource (X, 349 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Software engineering
Algorithms Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Software Engineering Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
ISBN | 3-540-32208-6 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | “Almost Stable” Matchings in the Roommates Problem -- On the Minimum Load Coloring Problem -- Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT -- The Hardness of Network Design for Unsplittable Flow with Selfish Users -- Improved Approximation Algorithm for Convex Recoloring of Trees -- Exploiting Locality: Approximating Sorting Buffers -- Approximate Fair Cost Allocation in Metric Traveling Salesman Games -- Rounding of Sequences and Matrices, with Applications -- A Note on Semi-online Machine Covering -- SONET ADMs Minimization with Divisible Paths -- The Conference Call Search Problem in Wireless Networks -- Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents -- Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost -- A Better-Than-Greedy Algorithm for k-Set Multicover -- Deterministic Online Optical Call Admission Revisited -- Scheduling Parallel Jobs with Linear Speedup -- Online Removable Square Packing -- The Online Target Date Assignment Problem -- Approximation and Complexity of k–Splittable Flows -- On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem -- Tighter Approximations for Maximum Induced Matchings in Regular Graphs -- On Approximating Restricted Cycle Covers -- A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs -- Speed Scaling of Tasks with Precedence Constraints -- Partial Multicuts in Trees -- Approximation Schemes for Packing with Item Fragmentation. |
Record Nr. | UNINA-9910483079503321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation and Online Algorithms [[electronic resource] ] : Second International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers / / edited by Giuseppe Persiano, Roberto Solis-Oba |
Edizione | [1st ed. 2005.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 |
Descrizione fisica | 1 online resource (VIII, 295 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence—Data processing Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Online Packet Switching -- Approximation Algorithms for Mixed Fractional Packing and Covering Problems -- Regular Papers -- Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees -- Online Bin Packing with Resource Augmentation -- A PTAS for Delay Minimization in Establishing Wireless Conference Calls -- This Side Up! -- Approximation Algorithm for Directed Multicuts -- Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria -- Approximation Algorithms for Spreading Points -- More Powerful and Simpler Cost-Sharing Methods -- Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints -- Priority Algorithms for Graph Optimization Problems -- Pricing Network Edges to Cross a River -- Submodular Integer Cover and Its Application to Production Planning -- Stochastic Online Scheduling on Parallel Machines -- A -Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path -- Order-Preserving Transformations and Greedy-Like Algorithms -- Off-line Admission Control for Advance Reservations in Star Networks -- Joint Base Station Scheduling -- Universal Bufferless Routing -- Strong Colorings of Hypergraphs -- Deterministic Monotone Algorithms for Scheduling on Related Machines -- Better Bounds for Minimizing SONET ADMs. |
Record Nr. | UNISA-996465950503316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation and Online Algorithms [[electronic resource] ] : Second International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers / / edited by Giuseppe Persiano, Roberto Solis-Oba |
Edizione | [1st ed. 2005.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 |
Descrizione fisica | 1 online resource (VIII, 295 p.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science - Mathematics Discrete mathematics Numerical analysis Computer graphics Artificial intelligence - Data processing Discrete Mathematics in Computer Science Numerical Analysis Computer Graphics Data Science |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Invited Talks -- Online Packet Switching -- Approximation Algorithms for Mixed Fractional Packing and Covering Problems -- Regular Papers -- Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees -- Online Bin Packing with Resource Augmentation -- A PTAS for Delay Minimization in Establishing Wireless Conference Calls -- This Side Up! -- Approximation Algorithm for Directed Multicuts -- Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria -- Approximation Algorithms for Spreading Points -- More Powerful and Simpler Cost-Sharing Methods -- Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints -- Priority Algorithms for Graph Optimization Problems -- Pricing Network Edges to Cross a River -- Submodular Integer Cover and Its Application to Production Planning -- Stochastic Online Scheduling on Parallel Machines -- A -Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path -- Order-Preserving Transformations and Greedy-Like Algorithms -- Off-line Admission Control for Advance Reservations in Star Networks -- Joint Base Station Scheduling -- Universal Bufferless Routing -- Strong Colorings of Hypergraphs -- Deterministic Monotone Algorithms for Scheduling on Related Machines -- Better Bounds for Minimizing SONET ADMs. |
Record Nr. | UNINA-9910767548803321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2005 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques [[electronic resource] ] : 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings / / edited by Maria Serna, Ronen Shaltiel, Klaus Jansen, José Rolim |
Edizione | [1st ed. 2010.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 |
Descrizione fisica | 1 online resource (XIII, 782 p. 54 illus.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Computer programming
Computer networks Computer science Algorithms Computer science—Mathematics Discrete mathematics Artificial intelligence—Data processing Programming Techniques Computer Communication Networks Theory of Computation Discrete Mathematics in Computer Science Data Science |
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. |
Record Nr. | UNISA-996466308103316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques [[electronic resource] ] : 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings / / edited by Maria Serna, Ronen Shaltiel, Klaus Jansen, José Rolim |
Edizione | [1st ed. 2010.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 |
Descrizione fisica | 1 online resource (XIII, 782 p. 54 illus.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Computer programming
Computer networks Computer science Algorithms Computer science—Mathematics Discrete mathematics Artificial intelligence—Data processing Programming Techniques Computer Communication Networks Theory of Computation Discrete Mathematics in Computer Science Data Science |
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. |
Record Nr. | UNINA-9910484749503321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques [[electronic resource] ] : 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013, Proceedings / / edited by Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, José D.P. Rolim |
Edizione | [1st ed. 2013.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 |
Descrizione fisica | 1 online resource (XIV, 716 p. 48 illus.) |
Disciplina | 005.1 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Computer science Numerical analysis Mathematical statistics Artificial intelligence—Data processing Discrete Mathematics in Computer Science Theory of Computation Numerical Analysis Probability and Statistics in Computer Science Data Science |
ISBN | 3-642-40328-X |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Spectral Sparsification in Dynamic Graph Streams -- The Online Stochastic Generalized Assignment Problem -- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems -- Approximating Large Frequency Moments with Pick-and-Drop Sampling -- Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams -- Capacitated Network Design on Undirected Graphs -- Scheduling Subset Tests: One-Time, Continuous, and How They Relate -- On the Total Perimeter of Homothetic Convex Bodies in a Convex Container -- Partial Interval Set Cover – Trade-Offs between Scalability and Optimality -- Online Square-into-Square Packing -- Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions -- Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems -- Multiple Traveling Salesmen in Asymmetric Metrics -- Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback -- The Approximability of the Binary Paintshop Problem -- Approximation Algorithms for Movement Repairmen -- Improved Hardness of Approximating Chromatic Number -- A Pseudo-approximation for the Genus of Hamiltonian Graphs -- A Local Computation Approximation Scheme to Maximum Matching -- Sketching Earth-Mover Distance on Graph Metrics -- Online Multidimensional Load Balancing -- A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs -- Interdiction Problems on Planar Graphs -- Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration -- Finding Heavy Hitters from Lossy or Noisy Data -- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy -- Phase Coexistence and Slow Mixing for the Hard-Core Model on Z2 -- Fast Private Data Release Algorithms for Sparse Queries -- Local Reconstructors and Tolerant Testers for Connectivity and Diameter -- An Optimal Lower Bound for Monotonicity Testing over Hypergrids -- Small-Bias Sets for Nonabelian Groups: Derandomizations of the Alon-Roichman Theorem -- What You Can Do with Coordinated Samples -- Robust Randomness Amplifiers: Upper and Lower Bounds -- The Power of Choice for Random Satisfiability -- Connectivity of Random High Dimensional Geometric Graphs -- Matching-Vector Families and LDCs over Large Modulo -- Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing -- Testing Membership in Counter Automaton Languages -- Tight Lower Bounds for Testing Linear Isomorphism -- Randomness-Efficient Curve Samplers -- Combinatorial Limitations of Average-Radius List Decoding -- Zero Knowledge LTCs and Their Applications -- A Tight Lower Bound for High Frequency Moment Estimation with Small Error -- Improved FPTAS for Multi-spin Systems -- Pseudorandomness for Regular Branching Programs via Fourier Analysis -- Absolutely Sound Testing of Lifted Codes -- On the Average Sensitivity and Density of k-CNF Formulas -- Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions. |
Record Nr. | UNISA-996465703803316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|