Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
The Journal of Supercomputing
Erschienen in: The Journal of Supercomputing 5/2019

02.11.2018

A linear time randomized approximation algorithm for Euclidean matching

verfasst von: Mahdi Imanparast, Seyed Naser Hashemi

Erschienen in: The Journal of Supercomputing | Ausgabe 5/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study the problem of computing Euclidean minimum weight matching which investigates the minimum weight perfect matching in a complete geometric graph on a set of 2n points in the plane. We propose a simple randomized approximation algorithm based on the geometrical aspect of the problem with O(n) expected time. The proposed algorithm computes a matching within at most 3 factors of the optimal solution. We also do some experimental tests to evaluate the performance of the proposed algorithm which indicate the efficiency of the proposed algorithm in finding the approximate matching in the practice.
Vorheriger Artikel SECM: status estimation and cache management algorithm in opportunistic networks
Nächster Artikel Insight into tiles generated by means of a correction technique

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
2.
Ball MO, Bodin LD, Dial R (1983) A matching based heuristic for scheduling mass transit crews and vehicles. Transp Sci 17:4–31CrossRef
3.
Derigs U, Metz A (1992) A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints. Oper Res Spektrum 14:91–106MathSciNetCrossRefMATH
4.
Bell CE (1994) Weighted matching with vertex weights: an application to scheduling training sessions in NASA space shuttle cockpit simulators. Eur J Oper Res 73:443–449CrossRefMATH
5.
Riskin EA, Lander R, Wang RY, Atlas LE (1994) Index assignment for progressive transmission of full-search vector quantization. IEEE Trans Image Proc 3:307–312CrossRef
6.
Zhu L, Zhao Y, Wang S, Chen H (2011) Spatial error concealment for stereoscopic video coding based on pixel matching. J Supercomput 58(1):96–105CrossRef
7.
Miller DL, Pekny JF (1995) A staged primal-dual algorithm for perfect b-matching with edge capacities. ORSA J Comput 7:298–320CrossRefMATH
8.
Lim JB, Jeong YS, Park DS, Lee HM (2018) An efficient distributed mutual exclusion algorithm for intersection traffic control. J Supercomput 74(3):1090–1107CrossRef
9.
Afgan E, Bangalore P, Skala T (2012) Scheduling and planning job execution of loosely coupled applications. J Supercomput 59(3):1431–1454CrossRef
10.
Choi HJ, Son DO, Kang SG, Kim JM, Lee HH, Kim CH (2013) An efficient scheduling scheme using estimated execution time for heterogeneous computing systems. J Supercomput 65(2):886–902CrossRef
11.
12.
13.
Gabow H (1973) Implementation of algorithms for maximum matching on non-bipartite graphs. PhD thesis, Stanford University
14.
Lawler EL (1976) Combinatorial optimization: networks and matroids. Holt, Rinehart, and Winston, New YorkMATH
15.
Gabow H, Galil Z, Micali S (1986) An \(O(EV log V)\) algorithm for finding a maximal weighted matching in general graphs. SIAM J Comput 15:120–130MathSciNetCrossRefMATH
16.
Gabow HN, Galil Z, Spencer TH (1989) Efficient implementation of graph algorithms using contraction. J ACM 36(3):540–572MathSciNetCrossRef
17.
Gabow HN (1990) Data structures for weighted matching and nearest common ancestors with linking. In: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp 434–443
18.
Edmonds J, Johnson EL, Lockhart SC (1969) Blossom I: A computer code for the matching problem. IBM T. J. Watson Research Center, Yorktown Heights, New York
19.
20.
Kolmogorov V (2009) Blossom V: a new implementation of a minimum cost perfect matching algorithm. Math Program Comput 1:43–67MathSciNetCrossRefMATH
21.
22.
Galil Z, Micali S, Gabow HN (1982) Priority queues with variable priority and an \(O(EV log V)\) algorithm for finding a maximal weighted matching in general graphs. In: Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’82), pp 255–261
23.
24.
25.
26.
Supowit KJ, Roingold EM (1983) Divide-and-Conquer heuristics for minimum weighted euclidean matching. SIAM J Comput 12(1):118–144MathSciNetCrossRefMATH
27.
Akl SG (1983) A note on Euclidean matchings, triangulations, and spanning trees. J Comb Inf Syst Sci 8(3):169–174MathSciNetMATH
28.
29.
Mirzaian A (1993) Minimum weight Euclidean matching and weighted relative neighborhood graphs. In: Proceedings of the 3rd Workshop on Algorithms and Data Structures (WADS’93), pp 506–517
30.
Varadarajan KR (1998) A divide-and-conquer algorithm for min-cost perfect matching in the plane. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS’98), pp 320–331
31.
32.
Arora S (1997) Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 38th Annual IEEE Symposium on Foundation of Computer Science (FOCS’97), pp 554–563
33.
Agarwal PK, Varadarajan KR (1999) Approximation algorithms for bipartite and non-bipartite matching in the plane. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’99), pp 805–814
34.
Rao SB, Smith WD (1998) Approximating geometrical graphs via “spanners” and “banyans”. In: Proceedings of the Annual ACM Symposium on Theory Computer (STOC’98), pp 540–550
35.
36.
Agarwal PK, Efrat A, Sharir, M (1995) Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. In: Proceedings of the 11th Annual Symposium on Computational Geometry (SoCG’95), pp 39–50
37.
Agarwal PK, Varadarajan KR (2004) A near-linear constant-factor approximation for euclidean bipartite matching? In: Proceedings of the 12th Annual Symposium on Computational Geometry (SoCG’04), pp 247–252
38.
Indyk P (2007) A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SoDA’07), pp 39–42
39.
Sharathkumar R, Agarwal PK (2012) A near-linear time \(\varepsilon \)-approximation algorithm for geometric bipartite matching. In: Proceedings of the 44th Annual ACM Symposium on Theory Computer (STOC’12), pp 385–394
40.
Sharathkumar R (2013) A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates. In: Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG’13), pp 9–16
41.
Agarwal PK, Sharathkumar R (2014) Approximation algorithms for bipartite matching with metric and geometric costs. In: Proceedings of the Annual ACM Symposium on Theory Computer (STOC’14), pp 555–564
42.
43.
Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press, Cambridge, pp 253–277MATH
44.
Metadaten
Titel
A linear time randomized approximation algorithm for Euclidean matching
verfasst von
Mahdi Imanparast
Seyed Naser Hashemi
Publikationsdatum
02.11.2018
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 5/2019
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-018-2673-2

Weitere Artikel der Ausgabe 5/2019

The Journal of Supercomputing 5/2019 Zur Ausgabe

OriginalPaper

Payload fragmentation framework for high-performance computing in cloud environment

OriginalPaper

Generic cooperative and distributed algorithm for recovery of signals with the same sparsity profile in wireless sensor networks: a non-convex approach

OriginalPaper

LP-WSC: a linear programming approach for web service composition in geographically distributed cloud environments

OriginalPaper

Wasted dynamic power and correlation to instruction set architecture for CPU throttling

OriginalPaper

Designing an efficient framework for vulnerability assessment and patching (VAP) in virtual environment of cloud computing

OriginalPaper

GPU parallelization of multigrid RANS solver for three-dimensional aerodynamic simulations on multiblock grids