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.
Algorithmics of matching under preferences / / David F. Manlove, University of Glasgow, UK ; with a foreword by Kurt Mehlhorn
| Algorithmics of matching under preferences / / David F. Manlove, University of Glasgow, UK ; with a foreword by Kurt Mehlhorn |
| Autore | Manlove David F |
| Pubbl/distr/stampa | [Hackensack] N.J., : World Scientific, c2013 |
| Descrizione fisica | 1 online resource (xxxi, 491 pages) |
| Disciplina | 005.1 |
| Collana | Series on theoretical computer science |
| Soggetto topico |
Matching theory
Marriage theorem Computer science - Mathematics |
| ISBN |
1-299-46251-0
981-4425-25-7 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Preface; Foreword; Acknowledgments; Contents; List of Figures; List of Tables; List of Algorithms; 1. Preliminary definitions, results and motivation; 1.1 Introduction; 1.1.1 Remit of this book; 1.1.1.1 Matching under preferences; 1.1.1.2 Free-for-all markets; 1.1.1.3 Centralised matching schemes; 1.1.2 The matching problems under consideration; 1.1.2.1 Classification of matching problems; 1.1.2.2 Bipartite matching problems with two-sided preferences; 1.1.2.3 Bipartite matching problems with one-sided preferences; 1.1.2.4 Non-bipartite matching problems with preferences
1.1.2.5 Further problem variants1.1.3 Existing literature on matching problems; 1.1.3.1 Algorithms and complexity literature; 1.1.3.2 Game theory and economics literature; 1.1.3.3 Algorithmic mechanism design literature; 1.1.4 Contribution of this book; 1.1.4.1 General overview; 1.1.4.2 Chapter outline; 1.1.4.3 What the book does not contribute; 1.1.5 Outline of this chapter; 1.2 Matchings in graphs; 1.3 The Hospitals / Residents problem (hr); 1.3.1 Introduction; 1.3.2 Key definitions; 1.3.3 Key results (up to 1989); 1.3.4 Stable Marriage problem (sm); 1.3.4.1 Key definitions 1.3.4.2 Key results (up to 1989)1.3.4.3 Rotations; 1.3.5 Hospitals / Residents problem with indifference; 1.3.6 Other variants of hr; 1.3.6.1 Couples; 1.3.6.2 Many-many stable matchings; 1.3.6.3 Master lists; 1.3.7 Motivation; 1.4 The Stable Roommates problem (sr); 1.4.1 Introduction; 1.4.2 Key definitions; 1.4.3 Key results (up to 1989); 1.4.4 Rotations; 1.4.5 Stable Roommates problem with indifference; 1.4.6 Motivation; 1.5 The House Allocation problem (ha) and its variants; 1.5.1 Introduction; 1.5.2 Formal definition of ha and hm; 1.5.3 Pareto optimal matchings 1.5.4 Maximum utility matchings1.5.5 Popular matchings; 1.5.6 Profile-based optimal matchings; 1.5.7 Extensions of ha; 1.5.8 Motivation; Stable Matching Problems; 2. The Stable Marriage problem: An update; 2.1 Introduction; 2.2 The 12 open problems of Gusfield and Irving; 2.2.1 Introduction; 2.2.2 1. Maximum number of stable matchings; 2.2.3 2. The "divorce digraph"; 2.2.4 3. Parallel algorithms for stable marriage; 2.2.5 4. Batch stability testing; 2.2.6 5. Structure of stable marriage with ties; 2.2.7 6. Sex-equal matching; 2.2.8 7. Lying and egalitarian matchings 2.2.9 10. Succinct certificates2.2.10 11. Algorithmic improvements; 2.3 The Subramanian and Feder papers; 2.3.1 Subramanian: sri and network stability; 2.3.2 Feder: sri and 2-sat; 2.3.3 Other fixed-point approaches; 2.4 Linear programming approaches; 2.5 Constraint programming approaches; 2.5.1 Introduction; 2.5.2 Preliminaries; 2.5.3 Overview of the csp model; 2.5.4 Arc consistency in the csp model; 2.6 Paths to stability; 2.6.1 Introduction; 2.6.2 The Roth-Vande Vate Mechanism; 2.6.3 The Random Order Mechanism; 2.6.4 Other decentralised algorithms; 2.7 Median stable matchings 2.8 Size versus stability |
| Record Nr. | UNINA-9910779692703321 |
Manlove David F
|
||
| [Hackensack] N.J., : World Scientific, c2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Algorithmics of matching under preferences / / David F. Manlove, University of Glasgow, UK ; with a foreword by Kurt Mehlhorn
| Algorithmics of matching under preferences / / David F. Manlove, University of Glasgow, UK ; with a foreword by Kurt Mehlhorn |
| Autore | Manlove David F |
| Pubbl/distr/stampa | [Hackensack] N.J., : World Scientific, c2013 |
| Descrizione fisica | 1 online resource (xxxi, 491 pages) |
| Disciplina | 005.1 |
| Collana | Series on theoretical computer science |
| Soggetto topico |
Matching theory
Marriage theorem Computer science - Mathematics |
| ISBN |
1-299-46251-0
981-4425-25-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Preface; Foreword; Acknowledgments; Contents; List of Figures; List of Tables; List of Algorithms; 1. Preliminary definitions, results and motivation; 1.1 Introduction; 1.1.1 Remit of this book; 1.1.1.1 Matching under preferences; 1.1.1.2 Free-for-all markets; 1.1.1.3 Centralised matching schemes; 1.1.2 The matching problems under consideration; 1.1.2.1 Classification of matching problems; 1.1.2.2 Bipartite matching problems with two-sided preferences; 1.1.2.3 Bipartite matching problems with one-sided preferences; 1.1.2.4 Non-bipartite matching problems with preferences
1.1.2.5 Further problem variants1.1.3 Existing literature on matching problems; 1.1.3.1 Algorithms and complexity literature; 1.1.3.2 Game theory and economics literature; 1.1.3.3 Algorithmic mechanism design literature; 1.1.4 Contribution of this book; 1.1.4.1 General overview; 1.1.4.2 Chapter outline; 1.1.4.3 What the book does not contribute; 1.1.5 Outline of this chapter; 1.2 Matchings in graphs; 1.3 The Hospitals / Residents problem (hr); 1.3.1 Introduction; 1.3.2 Key definitions; 1.3.3 Key results (up to 1989); 1.3.4 Stable Marriage problem (sm); 1.3.4.1 Key definitions 1.3.4.2 Key results (up to 1989)1.3.4.3 Rotations; 1.3.5 Hospitals / Residents problem with indifference; 1.3.6 Other variants of hr; 1.3.6.1 Couples; 1.3.6.2 Many-many stable matchings; 1.3.6.3 Master lists; 1.3.7 Motivation; 1.4 The Stable Roommates problem (sr); 1.4.1 Introduction; 1.4.2 Key definitions; 1.4.3 Key results (up to 1989); 1.4.4 Rotations; 1.4.5 Stable Roommates problem with indifference; 1.4.6 Motivation; 1.5 The House Allocation problem (ha) and its variants; 1.5.1 Introduction; 1.5.2 Formal definition of ha and hm; 1.5.3 Pareto optimal matchings 1.5.4 Maximum utility matchings1.5.5 Popular matchings; 1.5.6 Profile-based optimal matchings; 1.5.7 Extensions of ha; 1.5.8 Motivation; Stable Matching Problems; 2. The Stable Marriage problem: An update; 2.1 Introduction; 2.2 The 12 open problems of Gusfield and Irving; 2.2.1 Introduction; 2.2.2 1. Maximum number of stable matchings; 2.2.3 2. The "divorce digraph"; 2.2.4 3. Parallel algorithms for stable marriage; 2.2.5 4. Batch stability testing; 2.2.6 5. Structure of stable marriage with ties; 2.2.7 6. Sex-equal matching; 2.2.8 7. Lying and egalitarian matchings 2.2.9 10. Succinct certificates2.2.10 11. Algorithmic improvements; 2.3 The Subramanian and Feder papers; 2.3.1 Subramanian: sri and network stability; 2.3.2 Feder: sri and 2-sat; 2.3.3 Other fixed-point approaches; 2.4 Linear programming approaches; 2.5 Constraint programming approaches; 2.5.1 Introduction; 2.5.2 Preliminaries; 2.5.3 Overview of the csp model; 2.5.4 Arc consistency in the csp model; 2.6 Paths to stability; 2.6.1 Introduction; 2.6.2 The Roth-Vande Vate Mechanism; 2.6.3 The Random Order Mechanism; 2.6.4 Other decentralised algorithms; 2.7 Median stable matchings 2.8 Size versus stability |
| Record Nr. | UNINA-9910813941703321 |
|
Manlove David F
|
||
| [Hackensack] N.J., : World Scientific, c2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Algorithms - ESA 2008 [[electronic resource] ] : 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings / / edited by Kurt Mehlhorn
| Algorithms - ESA 2008 [[electronic resource] ] : 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings / / edited by Kurt Mehlhorn |
| Edizione | [1st ed. 2008.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 |
| Descrizione fisica | 1 online resource (XVII, 844 p.) |
| Disciplina | 511.8 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer programming
Computer networks Computer science Algorithms Numerical analysis Computer science—Mathematics Discrete mathematics Programming Techniques Computer Communication Networks Theory of Computation Numerical Analysis Discrete Mathematics in Computer Science |
| ISBN | 3-540-87744-4 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Lectures -- Flexible Path Planning Using Corridor Maps -- A Bridging Model for Multi-core Computing -- Contributed Papers -- Robust Kinetic Convex Hulls in 3D -- On Dominance Reporting in 3D -- Stabbing Convex Polygons with a Segment or a Polygon -- An Efficient Algorithm for 2D Euclidean 2-Center with Outliers -- A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry -- Cache-Oblivious Red-Blue Line Segment Intersection -- The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains -- Space-Time Tradeoffs for Proximity Searching in Doubling Spaces -- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem -- Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs -- Straight Skeletons of Three-Dimensional Polyhedra -- Randomized Competitive Analysis for Two-Server Problems -- Decompositions and Boundary Coverings of Non-convex Fat Polyhedra -- Approximating Multi-criteria Max-TSP -- An Integer Programming Algorithm for Routing Optimization in IP Networks -- A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling -- Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree -- Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors -- A Practical Quicksort Algorithm for Graphics Processors -- Bloomier Filters: A Second Look -- Coupled Path Planning, Region Optimization, and Applications in Intensity-Modulated Radiation Therapy -- A New Approach to Exact Crossing Minimization -- A Characterization of 2-Player Mechanisms for Scheduling -- A Local-Search 2-Approximation for 2-Correlation-Clustering -- The Alcuin Number of a Graph -- Time-Dependent SHARC-Routing -- Detecting Regular Visit Patterns -- Improved Approximation Algorithms for Relay Placement -- Selfish Bin Packing -- Improved Randomized Results for That Interval Selection Problem -- Succinct Representations of Arbitrary Graphs -- Edge Coloring and Decompositions of Weighted Graphs -- The Complexity of Sorting with Networks of Stacks and Queues -- Faster Steiner Tree Computation in Polynomial-Space -- Fitting a Step Function to a Point Set -- Faster Swap Edge Computation in Minimum Diameter Spanning Trees -- The Partial Augment–Relabel Algorithm for the Maximum Flow Problem -- An Optimal Dynamic Spanner for Doubling Metric Spaces -- RFQ: Redemptive Fair Queuing -- Range Medians -- Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves -- Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison -- On the Complexity of Optimal Hotlink Assignment -- Oblivious Randomized Direct Search for Real-Parameter Optimization -- Path Minima in Incremental Unrooted Trees -- Improved Competitive Performance Bounds for CIOQ Switches -- Two-Stage Robust Network Design with Exponential Scenarios -- An Optimal Incremental Algorithm for Minimizing Lateness with Rejection -- More Robust Hashing: Cuckoo Hashing with a Stash -- Better and Simpler Approximation Algorithms for the Stable Marriage Problem -- Edit Distances and Factorisations of Even Permutations -- Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count -- Facility Location in Dynamic Geometric Data Streams -- The Effects of Local Randomness in the Adversarial Queueing Model -- Parallel Imaging Problem -- An Online Algorithm for Finding the Longest Previous Factors -- Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions -- Improved BDD Algorithms for the Simulation of Quantum Circuits -- Mobile Route Planning -- How Reliable Are Practical Point-in-Polygon Strategies? -- Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach -- Approximability of Average Completion Time Scheduling on Unrelated Machines -- Relative Convex Hulls in Semi-dynamic Subdivisions -- An Experimental Analysis of Robinson-Foulds Distance Matrix Algorithms -- On the Size of the 3D Visibility Skeleton: Experimental Results -- An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions -- Deterministic Sampling Algorithms for Network Design. |
| Record Nr. | UNISA-996465432103316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms - ESA 2008 : 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings / / edited by Kurt Mehlhorn
| Algorithms - ESA 2008 : 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings / / edited by Kurt Mehlhorn |
| Edizione | [1st ed. 2008.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 |
| Descrizione fisica | 1 online resource (XVII, 844 p.) |
| Disciplina | 511.8 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer programming
Computer networks Computer science Algorithms Numerical analysis Computer science - Mathematics Discrete mathematics Programming Techniques Computer Communication Networks Theory of Computation Numerical Analysis Discrete Mathematics in Computer Science |
| ISBN | 3-540-87744-4 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Lectures -- Flexible Path Planning Using Corridor Maps -- A Bridging Model for Multi-core Computing -- Contributed Papers -- Robust Kinetic Convex Hulls in 3D -- On Dominance Reporting in 3D -- Stabbing Convex Polygons with a Segment or a Polygon -- An Efficient Algorithm for 2D Euclidean 2-Center with Outliers -- A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry -- Cache-Oblivious Red-Blue Line Segment Intersection -- The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains -- Space-Time Tradeoffs for Proximity Searching in Doubling Spaces -- A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem -- Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs -- Straight Skeletons of Three-Dimensional Polyhedra -- Randomized Competitive Analysis for Two-Server Problems -- Decompositions and Boundary Coverings of Non-convex Fat Polyhedra -- Approximating Multi-criteria Max-TSP -- An Integer Programming Algorithm for Routing Optimization in IP Networks -- A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling -- Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree -- Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors -- A Practical Quicksort Algorithm for Graphics Processors -- Bloomier Filters: A Second Look -- Coupled Path Planning, Region Optimization, and Applications in Intensity-Modulated Radiation Therapy -- A New Approach to Exact Crossing Minimization -- A Characterization of 2-Player Mechanisms for Scheduling -- A Local-Search 2-Approximation for 2-Correlation-Clustering -- The Alcuin Number of a Graph -- Time-Dependent SHARC-Routing -- Detecting Regular Visit Patterns -- Improved Approximation Algorithms for Relay Placement -- Selfish Bin Packing -- Improved Randomized Results for That Interval Selection Problem -- Succinct Representations of Arbitrary Graphs -- Edge Coloring and Decompositions of Weighted Graphs -- The Complexity of Sorting with Networks of Stacks and Queues -- Faster Steiner Tree Computation in Polynomial-Space -- Fitting a Step Function to a Point Set -- Faster Swap Edge Computation in Minimum Diameter Spanning Trees -- The Partial Augment–Relabel Algorithm for the Maximum Flow Problem -- An Optimal Dynamic Spanner for Doubling Metric Spaces -- RFQ: Redemptive Fair Queuing -- Range Medians -- Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves -- Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison -- On the Complexity of Optimal Hotlink Assignment -- Oblivious Randomized Direct Search for Real-Parameter Optimization -- Path Minima in Incremental Unrooted Trees -- Improved Competitive Performance Bounds for CIOQ Switches -- Two-Stage Robust Network Design with Exponential Scenarios -- An Optimal Incremental Algorithm for Minimizing Lateness with Rejection -- More Robust Hashing: Cuckoo Hashing with a Stash -- Better and Simpler Approximation Algorithms for the Stable Marriage Problem -- Edit Distances and Factorisations of Even Permutations -- Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count -- Facility Location in Dynamic Geometric Data Streams -- The Effects of Local Randomness in the Adversarial Queueing Model -- Parallel Imaging Problem -- An Online Algorithm for Finding the Longest Previous Factors -- Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions -- Improved BDD Algorithms for the Simulation of Quantum Circuits -- Mobile Route Planning -- How Reliable Are Practical Point-in-Polygon Strategies? -- Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach -- Approximability of Average Completion Time Scheduling on Unrelated Machines -- Relative Convex Hulls in Semi-dynamic Subdivisions -- An Experimental Analysis of Robinson-Foulds Distance Matrix Algorithms -- On the Size of the 3D Visibility Skeleton: Experimental Results -- An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions -- Deterministic Sampling Algorithms for Network Design. |
| Record Nr. | UNINA-9910146568503321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2008 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||