AncomWiki

Online Graph Edge-Coloring in the Random-Order Arrival Model

Properties1
description이 논문은 최대 차수가 Δ인 그래프의 온라인 엣지 컬러링 문제를 다룹니다. 기존 그리디 알고리즘의 근사 계수 2를 개선하여, 랜덤 순서 도착 모델에서 Δ=Ω(log n)인 경우 (1+e²/(e²-1)+o(1))Δ ≈ 1.43Δ개의 색상을 사용하여 고 확률로 컬러링할 수 있음을 보였습니다. 이는 Panconesi와 Srinivasan의 분산 오프라인 알고리즘을 확장하고 실패한 색상을 재사용하는 방식으로 달성되었습니다. 색상 재…

11 min read

Online Graph Edge-Coloring in the Random-Order Arrival Model

Source

  • Evernote/Papers/Online Graph Edge-Coloring in the Random-Order Arrival Model.md

Summary

이 논문은 최대 차수가 Δ인 그래프의 온라인 엣지 컬러링 문제를 다룹니다. 기존 그리디 알고리즘의 근사 계수 2를 개선하여, 랜덤 순서 도착 모델에서 Δ=Ω(log n)인 경우 (1+e²/(e²-1)+o(1))Δ ≈ 1.43Δ개의 색상을 사용하여 고 확률로 컬러링할 수 있음을 보였습니다. 이는 Panconesi와 Srinivasan의 분산 오프라인 알고리즘을 확장하고 실패한 색상을 재사용하는 방식으로 달성되었습니다. 색상 재사용 횟수를 늘리면 근사 계수가 더 낮아지며(예: 5회 재사용 시 1.26Δ), O(log(Δ/log n))회 재사용 시 거의 최적의 Δ+o(Δ) 색상 사용이 가능할 것으로 추측합니다.

Key Points

  • 온라인 엣지 컬러링 문제에서 기존 그리디 알고리즘의 근사 계수 2를 개선함
  • 랜덤 순서 도착 모델에서 Δ=Ω(log n)일 때 약 1.43Δ 색상으로 컬러링 가능함을 증명
  • 실패한 색상 재사용을 통해 근사 계수 감소 (5회 재사용 시 1.26Δ)
  • O(log(Δ/log n))회 재사용 시 거의 최적의 Δ+o(Δ) 색상 사용 가능성 추측

그래프 뷰

백링크