Approximation Algorithms for Clustering and Vehicle Routing
聚类和车辆路径的近似算法
基本信息
- 批准号:RGPIN-2020-04043
- 负责人:
- 金额:$ 3.5万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2020
- 资助国家:加拿大
- 起止时间:2020-01-01 至 2021-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Challenging optimization problems appear in many aspects of our society. For example, how should one schedule a fleet of vehicles to deliver thousands of packages in a day? How can we allocate hundreds of courses to various classrooms on campus while respecting a number of auxiliary constraints such as avoiding overlap between courses that are likely to be taken by the same students? How can we place components on a circuit board and connect them via wires while keeping the entire board as small as possible? Further challenges are easy to find in many other subjects: airport scheduling, data clustering, medical testing, mobile aid station placement, etc. Poor solutions can sometimes result in millions of dollars lost.
Many of these problems are so large that we rely on algorithms to find their solutions. Unfortunately, the models we use to address these problems are provably hard; being able to efficiently find the optimum solution with an algorithm would yield an unexpected resolution to the fundamental P vs. NP problem in computing science. Despite this barrier, we still need to address these important problems.
To cope with this difficulty, I design approximation algorithms for hard optimization problems. These are efficient algorithms that find near-optimal solutions. This is not a mere heuristic statement, such algorithms also come with a proof that the cost of solutions they produce are within some bounded error of the best possible solution's cost. With such an approach, we have confidence that the algorithms we design are guaranteed to perform well when used on data sets that may not have been considered when the algorithm was designed.
This research focuses on two very common classes of problems: data clustering and vehicle routing. Data clustering is used to support the results in hundreds of research papers every year with applications stemming from data mining, machine learning, image processing, statistical analysis, big data visualization, etc. Other applications include operations research, for example when we want to place distribution centres to serve clients in a cost-effective manner. The algorithms that are used in practice typically work well, but are known to perform poorly in certain instances. My work will focus on designing improved approximations for clustering models that, provably, work well in every instance of the problem. I am also interested in articulating, from a fundamental point of view, why certain algorithms perform better than their worst-case guarantees on "real-world" data.
My work on vehicle routing will focus on improving service times and operating costs by designing improved approximations for some fundamental models beyond the well-known Traveling Salesperson Problem. Further, how do solutions to these models relate? How can solving one vehicle routing problem provide better approximation algorithms for other models?
具有挑战性的优化问题出现在我们社会的许多方面。例如,如何安排车队在一天内运送数千个包裹?我们如何将数百门课程分配到校园的各个教室,同时尊重一些辅助约束,例如避免可能由同一学生选修的课程之间的重叠?我们如何在电路板上放置组件并通过电线连接它们,同时保持整个电路板尽可能小?在许多其他学科中也很容易发现进一步的挑战:机场调度、数据聚类、医疗测试、移动救护站安置等。糟糕的解决方案有时会导致数百万美元的损失。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Friggstad, Zachary其他文献
Minimizing Movement in Mobile Facility Location Problems
- DOI:
10.1145/1978782.1978783 - 发表时间:
2011-07-01 - 期刊:
- 影响因子:1.3
- 作者:
Friggstad, Zachary;Salavatipour, Mohammad R. - 通讯作者:
Salavatipour, Mohammad R.
Friggstad, Zachary的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Friggstad, Zachary', 18)}}的其他基金
Approximation Algorithms for Clustering and Vehicle Routing
聚类和车辆路径的近似算法
- 批准号:
RGPIN-2020-04043 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for Clustering and Vehicle Routing
聚类和车辆路径的近似算法
- 批准号:
RGPAS-2020-00075 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Accelerator Supplements
Approximation Algorithms for Clustering and Vehicle Routing
聚类和车辆路径的近似算法
- 批准号:
RGPAS-2020-00075 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Accelerator Supplements
Approximation Algorithms for Clustering and Vehicle Routing
聚类和车辆路径的近似算法
- 批准号:
RGPIN-2020-04043 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Approximation Algorithms for Clustering and Vehicle Routing
聚类和车辆路径的近似算法
- 批准号:
RGPAS-2020-00075 - 财政年份:2020
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Accelerator Supplements
Canada Research Chair in Combinatorial Optimization
加拿大组合优化研究主席
- 批准号:
1000230198-2014 - 财政年份:2019
- 资助金额:
$ 3.5万 - 项目类别:
Canada Research Chairs
Improved Mathematical Programming Techniques for Approximation Algorithms
改进近似算法的数学编程技术
- 批准号:
RGPIN-2015-06496 - 财政年份:2019
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Canada Research Chair in Combinatorial Optimization
加拿大组合优化研究主席
- 批准号:
1000230198-2014 - 财政年份:2018
- 资助金额:
$ 3.5万 - 项目类别:
Canada Research Chairs
Improved Mathematical Programming Techniques for Approximation Algorithms
改进近似算法的数学编程技术
- 批准号:
RGPIN-2015-06496 - 财政年份:2018
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Improved Mathematical Programming Techniques for Approximation Algorithms
改进近似算法的数学编程技术
- 批准号:
RGPIN-2015-06496 - 财政年份:2017
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
CAREER: A Theoretical Exploration of Efficient and Accurate Clustering Algorithms
职业生涯:高效准确聚类算法的理论探索
- 批准号:
2337832 - 财政年份:2024
- 资助金额:
$ 3.5万 - 项目类别:
Continuing Grant
AF: Small: New Challenges and Approaches in Clustering Algorithms
AF:小:聚类算法的新挑战和方法
- 批准号:
2311397 - 财政年份:2023
- 资助金额:
$ 3.5万 - 项目类别:
Standard Grant
Physics-Inspired Graph Clustering Algorithms
受物理启发的图聚类算法
- 批准号:
2748617 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Studentship
Development of Algorithms for Ultrametric Tree Optimization and Hierarchical Clustering Optimization
超度量树优化和层次聚类优化算法的开发
- 批准号:
22K11921 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Approximation Algorithms for Clustering and Vehicle Routing
聚类和车辆路径的近似算法
- 批准号:
RGPIN-2020-04043 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
Clustering and semi-supervised learning on large heterogeneous graphs: Mathematical formulations and numerical optimization algorithms
大型异构图上的聚类和半监督学习:数学公式和数值优化算法
- 批准号:
569398-2022 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Alexander Graham Bell Canada Graduate Scholarships - Doctoral
Approximation Algorithms for Clustering and Vehicle Routing
聚类和车辆路径的近似算法
- 批准号:
RGPAS-2020-00075 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Accelerator Supplements
A comparative study of clustering algorithms in ancestral genome reconstruction
祖先基因组重建中聚类算法的比较研究
- 批准号:
574917-2022 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
University Undergraduate Student Research Awards
(Re)designing Clustering Algorithms for Big Data
(重新)设计大数据聚类算法
- 批准号:
RGPIN-2017-05617 - 财政年份:2022
- 资助金额:
$ 3.5万 - 项目类别:
Discovery Grants Program - Individual
A comprehensive study of big data clustering algorithms
大数据聚类算法综合研究
- 批准号:
571110-2018 - 财政年份:2021
- 资助金额:
$ 3.5万 - 项目类别:
Alexander Graham Bell Canada Graduate Scholarships - Master's