Diagram med avgränsad motorvägsdimension introducerades av Abraham m.fl. [SODA 2010] som modell för transportnät. Vi visar att varje sådan graf kan inbäddas i en fördelning över avgränsade trädbredd grafer med godtyckligt liten förvrängning. Mer konkret, med tanke på en viktad graf G = (V, E) av konstant vägdimension, visar vi hur man slumpmässigt beräknar en viktad graf H = (V, E ) som förvränger kortaste vägavstånd av G med högst en 1 + ε faktor i förväntan, och vars trädbredd är polylogaritmisk i proportion till G. Vår probabilistiska inbäddning innebär kvasi-polynom tid approximation system för ett antal optimeringsproblem som naturligt uppstår i transportnät, inklusive Travelling Salesman, Steiner Tree, och Facility Plats. För att bygga vår inbäddning för grafer med låga motorvägsdimensioner förlänger vi Talwars [STOC 2004] inbäddning av mått med låga dubbleringsdimensioner i avgränsade grafer med trädbredd, vilket generaliserar kända resultat för euklideiska mått. Vi lägger till flera icke-triviala ingredienser till Talwars tekniker, och i synnerhet noggrant analysera strukturen av grafer med låg motorvägsdimension. Således visar vi att den geometriska verktygslåda som används för Euclideans mått sträcker sig bortom klassen av låga dubbleringsmått.
Feldmann m.fl. REF upptäckte nästan-polynom-tids approximationssystem för Traveling Salesman, Steiner Tree och Facility Location.
A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}