Ett linjärt arrangemang av en n-vertex graf är en en-till-en kartläggning av dess hörn till heltal f1; : : ; ng. Bandbredden för ett linjärt arrangemang är den maximala skillnaden mellan karterade värden för intilliggande hörn. Problemet med nding ett linjärt arrangemang med minsta möjliga bandbredd i NP-hård. Vi presenterar en randomiserad algoritm som löper i nästan linjär tid och ger ett linjärt arrangemang vars bandbredd ligger inom en polylogaritmisk multiplikativ faktor av optimal. Vår algoritm bygger på en ny idé, kallad volym som respekterar inbäddningar, vilket är en naturlig förlängning av små förvrängningar av Bourgain och Linial, London och Rabinovich.
Analysen av alla dessa algoritmer bygger på begreppet volym som respekterar inbäddningar som infördes i REF.
Approximating the Bandwidth via Volume Respecting Embeddings
{'venue': 'J. Comput. Syst. Sci.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}