Orientering är följande optimering problem: med tanke på en kant-viktad graf (riktad eller oriktad), två noder s, t och en tidsgräns T, hitta en s-t gång av total längd på de flesta T som maximerar antalet olika noder som besöks av promenaden. Man får en generalisering, nämligen orientering med tidsfönster (även kallad TSP med tidsfönster), om varje nod v har ett angivet tidsfönster [R(v, D(v)] och en nod v räknas som besöks av promenaden endast om v besöks under dess tidsfönster. För tidsfönstret problem, en O(log OPT) approximation kan uppnås även för riktade grafer om algoritmen är tillåten kvasi-polynom tid. Men de mest kända polynom tid approximation förhållandet är O(log 2 OPT) för oriktade grafer och O(log 4 OPT) i riktade grafer. I detta dokument gör vi vissa framsteg mot att minska denna diskrepans, och i processen få förbättrade approximationskvoter i flera naturliga miljöer. Låt våra resultat ges nedan med α som anger den kända approximationsförhållandet för orientering (utan tidsfönster). För närvarande α = (2 + ) för oriktade grafer och α = O(log 2 OPT) i riktade grafer. • En O(α log L max ) approximation när R(v) och D(v) är heltal värderas för varje v. • En O(α max {log OPT, log Lmax Lmin }) approximation. • En O(α log Lmax Lmin ) approximation när inga start- och slutpunkter anges. I synnerhet, om Lmin är poly-bundet, vi få en O(log n) approximation för tid-fönster problem i oriktade grafer.
En O(log L)-uppskattning anges i REF, för fallet att alla tidsfönster start och sluttider är heltal, där L är längden på den längsta tidsfönstret.
Approximation Algorithms for Orienteering with Time Windows
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}