On a Greedy Heuristic for Complete Matching

No abstract is available for this paper.

• Publication year

  1981

• Venue

  SIAM journal on computing (Print)

• Publication date

  1981-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/0210050
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combinatorial Optimization: Algorithms and Complexity

  1981cited by this paper
• Heuristics for weighted perfect matching

  1980cited by this paper
• Combinatorial Algorithms: Theory and Practice

  1977cited by this paper
• An Analysis of Several Heuristics for the Traveling Salesman Problem

  1977cited by this paper
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane

  1977cited by this paper
• Closest-point problems

  1975cited by this paper
• Two dimensional wave propagation through nonlinear media

  1969cited by this paper
• STRESS WAVES IN LAYERED ARBITRARY MEDIA SLAM CODE FREE-FIELD STUDY. VOLUME IV. AUXILIARY PROGRAMS.

  1968cited by this paper
• Linear programming and extensions

  1965cited by this paper

• Proof of a finite threshold for the union-find decoder

  2026cites this paper
• Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair

  2025cites this paper
• A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays

  2025cites this paper
• Fast 1-Wasserstein distance approximations using greedy strategies

  2024influential citation
• Data-Dependent LSH for the Earth Mover’s Distance

  2024cites this paper
• Enhancing selectivity using Wasserstein distance based reweighing

  2024influential citation
• Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line

  2024cites this paper
• Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching

  2024cites this paper
• Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings

  2023cites this paper
• Demystifying Statistical Matching Algorithms for Big Data

  2023cites this paper
• SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems

  2022cites this paper
• Some applications of concentration of measure type results to genomics and drug discovery

  2022cites this paper
• Display of 3D Illuminations using Flying Light Specks

  2022cites this paper
• Enhancing molecular selectivity using Wasserstein distance based reweighing

  2022influential citation
• Matching through Embedding in Dense Graphs

  2020influential citation
• regular

  2020cites this paper
• Probabilistic Analysis of Optimization Problems on Sparse Random Shortest Path Metrics

  2020cites this paper
• Pairing Things Off: Counting Stable Matchings, Finding Your Ride, and Designing Tournaments

  2020cites this paper
• Analysis of Heuristics with Random Shortest Path Metrics on Sparse Graphs

  2020cites this paper
• A queueing-theoretic model for resource allocation in one-dimensional distributed service network

  2019cites this paper
• AQueueing-theoretic Model for Resource Allocation in One-dimensional Distributed Service Networks

  2019cites this paper
• Resource Allocation in One-Dimensional Distributed Service Networks

  2019cites this paper
• Fmding a Cheap Matching THC

  2018cites this paper
• Deterministic Min-Cost Matching with Delays

  2018influential citation
• Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics

  2018cites this paper
• Maintaining Perfect Matchings at Low Cost

  2018cites this paper
• Probabilistic analysis of optimization problems in random shortest path metrics applied to Erdős–Rényi random graphs

  2018influential citation
• Optimisation for large-scale maintenance, scheduling and vehicle routing problems

  2017influential citation
• A Match in Time Saves Nine: Deterministic Online Matching With Delays

  2017cites this paper
• Exact and asymptotic solutions of the recurrence

  2016cites this paper
• A Comparison of One-Pass and Bi-directional Approaches Applied to Large-Scale Road Inspection

  2016cites this paper
• Efficient Large-scale Road Inspection Routing

  2016cites this paper
• Online matching: haste makes waste!

  2016cites this paper
• Collaboration in distributed systems: robots, ants, and matchings

  2015cites this paper
• Why are certain polynomials hard?: A look at non-commutative, parameterized and homomorphism polynomials

  2015cites this paper
• The Price of Matching with Metric Preferences

  2015cites this paper
• Linear-Time Approximation for Maximum Weight Matching

  2014cites this paper
• Approximation algorithms for bipartite matching with metric and geometric costs

  2014cites this paper
• A on\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${o}\mathopen {}\left( n\right) \mathclose {}$$\end{document}-Compe

  2014cites this paper
• A Randomized O(log2k)-Competitive Algorithm for Metric Bipartite Matching

  2014influential citation
• Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems

  2013cites this paper
• The Greedy Algorithm

  2013cites this paper
• Optimizing the experimental design of texture goniometry

  2012cites this paper
• The Price of Matching Selfish Vertices

  2011influential citation
• Scaling algorithms for approximate and exact maximum weight matching

  2011cites this paper
• Batch testing, adaptive algorithms, and heuristic applications for stable marriage problems

  2010cites this paper
• Combinatorics, Automata and Number Theory

  2010cites this paper
• Distributed resource management and matching in sensor networks

  2009cites this paper
• To appear in : Approximation Algorithms

  2007cites this paper
• Parallel Algorithms in Graph Theory and Algebra 4 Studying Complexities of Genetic Algorithms 89

  2007cites this paper
• Scheduling algorithms for throughput maximization in data networks

  2007cites this paper
• An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching

  2007cites this paper
• Distributed Coordination Collecting, Locking, and Matching

  2006cites this paper
• Digital Sums and Divide-and-Conquer Recurrences: Fourier Expansions and Absolute Convergence

  2005cites this paper
• Lazy Algorithms for Dynamic Closest Pair with Arbitary Distance Measures

  2004cites this paper
• Local spatio-temporal image features for motion interpretation

  2004cites this paper
• Fast and Simple Algorithms for Weighted Perfect Matching

  2004cites this paper
• An asymptotic theory for recurrence relations based on minimization and maximization

  2003cites this paper
• The ring of k-regular sequences, II

  2003cites this paper
• A genetic-based framework for solving (multi-criteria) weighted matching problems

  2003cites this paper
• Matching: Arc Routing and the Solution Connection

  2000cites this paper
• An Experimental Comparison of Parallel Algorithms for Ear Decomposition of Graphs using Two Leading Paradigms

  2000cites this paper
• Computing MinimumWeight Perfect Matchings

  1999cites this paper
• Fast hierarchical clustering and other applications of dynamic closest pairs

  1999cites this paper
• A Practical Parallel Algorithm for Cycle Detection in Partitioned Digraphs

  1999cites this paper
• Computing Minimum-Weight Perfect Matchings

  1999cites this paper
• A Practical Parallel Algorithm for Cycle Detection in Partitioned

  1999cites this paper
• The primal-dual method for approximation algorithms and its application to network design problems

  1996cites this paper
• Chapter 3 Matching

  1995cites this paper
• New primal and dual matching heuristics

  1995cites this paper
• Some recent results in the analysis of greedy algorithms for assignment problems

  1994cites this paper
• Approximating Minimum Weight Perfect Matchings for Complete Graphs Satisfying the Triangle Inequality

  1993cites this paper
• Minmax recurrences in analysis of algorithms

  1993cites this paper
• A general class of heuristics for constrained forest and cycle problems

  1993cites this paper
• Online Weighted Matching

  1993cites this paper
• A general approximation technique for constrained forest problems

  1992influential citation
• Competitive paging and dual-guided on-line weighted caching and watching algorithms

  1992cites this paper
• An efficient parallel algorithm for the assignment problem on the plane

  1992cites this paper
• Application of stepwise clustering method for the determination of efficient assembly sequence

  1992cites this paper
• On-line weighted matching

  1991influential citation
• Probability and statisitics in the service of computer science: illustrations using the assignment problem

  1990cites this paper
• Worst-case greedy matchings in the unit d-cube

  1990cites this paper
• Greedy Matching on the Line

  1990cites this paper
• New techniques for some dynamic closest-point and farthest-point problems

  1990cites this paper
• The bisection width of grid graphs

  1990cites this paper
• Heuristic methods and applications: A categorized survey

  1989cites this paper
• Greedy matching on a grid

  1988cites this paper
• A new class of heuristic algorithms for weighted perfect matching

  1988cites this paper
• Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching

  1988influential citation
• Approximation Algorithms for Weighted Matching

  1987cites this paper
• A Lower Bound to the Complexity of Euclidean and Rectilinear Matching Algorithms

  1986cites this paper
• Bibliography on quadtrees and related hierarchical data structures

  1986cites this paper
• Data Structures for Raster Graphics

  1986cites this paper
• Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem

  1986cites this paper
• On the existence of weak greedy matching heuristics

  1986cites this paper
• Practical use of Bucketing Techniques in Computational Geometry

  1985cites this paper
• A scaling algorithm for weighted matching on general graphs

  1985cites this paper
• Recurrence relations based on minimization and maximization

  1985cites this paper
• A Partitioning Algorithm for Minimum Weighted Euclidean Matching

  1984cites this paper
• Optimale Zuordnungen und Matchings: Anwendungen, Grundlagen und Verfahren

  1983cites this paper