서브메뉴
검색
The Fine-Grained Complexity of Min-Distance Problems in DAGs
The Fine-Grained Complexity of Min-Distance Problems in DAGs
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202103047
- ISBN
- 9798280712492
- DDC
- 510
- 저자명
- Kaufmann, Jenny.
- 서명/저자
- The Fine-Grained Complexity of Min-Distance Problems in DAGs
- 발행사항
- [Sl] : Harvard University, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 91 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-12, Section: B.
- 주기사항
- Advisor: Vassilevska Williams, Virginia;Sudan, Madhu.
- 학위논문주기
- Thesis (Ph.D.)--Harvard University, 2025.
- 초록/해제
- 요약The min-distance between two nodes u and v is the minimum of the shortest path distances from u to v and from v to u. Min-distance is a natural measure of distance in DAGs (directed acyclic graphs), and many classically studied graph distance parameters can be redefined in terms of min-distance. This thesis presents several new results on the fine-grained complexity of approximating min-distance parameters such as min-diameter, min-radius, and min-eccentricities, concentrating primarily (though not exclusively) on the special case of DAGs. In particular, we develop new approximation algorithms for these parameters, with runtimes polynomially faster than the standard All-Pairs Shortest Paths algorithm. Our algorithms improve on the approximation factors achieved in prior work, and in several cases, we obtain approximation factors that are conditionally tight, in the sense that they match lower bounds implied by hardness hypotheses such as the Orthogonal Vectors Conjecture and the Hitting Set Conjecture. We also obtain new several conditional lower bounds for min-distance problems, including a new lower bound for min-diameter conditioned on the OV Conjecture. Lastly, we present the first study of approximating bichromatic min-diameter.This thesis is based on work originally published in [DK21] and [BKV23].
- 일반주제명
- Mathematics
- 일반주제명
- Computer science
- 일반주제명
- Applied mathematics
- 키워드
- Algorithms
- 키워드
- Graph theory
- 키워드
- Acyclic graphs
- 기타저자
- Harvard University Mathematics
- 기본자료저록
- Dissertations Abstracts International. 86-12B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017356843
■00520260202103047
■006m o d
■007cr#unu||||||||
■020 ▼a9798280712492
■035 ▼a(MiAaPQ)AAI31930983
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a510
■1001 ▼aKaufmann, Jenny.▼0(orcid)0000-0002-6629-0341
■24510▼aThe Fine-Grained Complexity of Min-Distance Problems in DAGs
■260 ▼a[Sl]▼bHarvard University▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a91 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-12, Section: B.
■500 ▼aAdvisor: Vassilevska Williams, Virginia;Sudan, Madhu.
■5021 ▼aThesis (Ph.D.)--Harvard University, 2025.
■520 ▼aThe min-distance between two nodes u and v is the minimum of the shortest path distances from u to v and from v to u. Min-distance is a natural measure of distance in DAGs (directed acyclic graphs), and many classically studied graph distance parameters can be redefined in terms of min-distance. This thesis presents several new results on the fine-grained complexity of approximating min-distance parameters such as min-diameter, min-radius, and min-eccentricities, concentrating primarily (though not exclusively) on the special case of DAGs. In particular, we develop new approximation algorithms for these parameters, with runtimes polynomially faster than the standard All-Pairs Shortest Paths algorithm. Our algorithms improve on the approximation factors achieved in prior work, and in several cases, we obtain approximation factors that are conditionally tight, in the sense that they match lower bounds implied by hardness hypotheses such as the Orthogonal Vectors Conjecture and the Hitting Set Conjecture. We also obtain new several conditional lower bounds for min-distance problems, including a new lower bound for min-diameter conditioned on the OV Conjecture. Lastly, we present the first study of approximating bichromatic min-diameter.This thesis is based on work originally published in [DK21] and [BKV23].
■590 ▼aSchool code: 0084.
■650 4▼aMathematics
■650 4▼aComputer science
■650 4▼aApplied mathematics
■653 ▼aAlgorithms
■653 ▼aComputational complexity
■653 ▼aGraph theory
■653 ▼aAcyclic graphs
■653 ▼aHitting Set Conjecture
■690 ▼a0405
■690 ▼a0984
■690 ▼a0364
■71020▼aHarvard University▼bMathematics.
■7730 ▼tDissertations Abstracts International▼g86-12B.
■790 ▼a0084
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17356843▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
