Probabilistisk analys för metriska optimeringsproblem har främst utförts på slumpmässiga Euclidean fall, men lite är känt om metriska fall som hämtats från andra distributioner än Euclidean. Detta motiverar vår studie av slumpmässiga metriska fall för optimeringsproblem som erhålls enligt följande: Varje kant i en komplett graf får en vikt ritad självständigt på måfå. Avståndet mellan två noder är då längden på en kortaste väg (med avseende på de dragna vikterna) som förbinder dessa noder. Vi bevisar strukturella egenskaper hos de slumpmässiga kortaste vägmått som genereras på detta sätt. Vårt viktigaste strukturella bidrag är byggandet av en bra klusterbildning. Sedan tillämpar vi dessa resultat för att analysera approximation av heuristik för matchning, den resande säljare problem (TSP), och k-median problem, liksom körtiden för 2-opt heuristic för TSP. De gränser som vi får är betydligt bättre än respektive värsta fall gränser. Detta tyder på att slumpmässiga kortaste vägmått är enkla fall, liknande slumpmässiga Euclidean fall, om än av helt olika strukturella skäl.
Bringmann m.fl. REF använde denna modell på hela grafen för att analysera heuristik för matchning, TSP och k-median.
Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}