Fixed-parameter tractability for geometric optimization problems

几何优化问题的固定参数易处理性

• 批准号: EP/N029143/1
• 负责人: Panagiotis Giannopoulos
• 金额: $ 12.21万
• 依托单位: Middlesex University
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2016
• 资助国家: 英国
• 起止时间: 2016 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FN029143%2F1
• 关键词: Fixed; parameter; tractability; geometric; optimization

Many real-world problems can be formulated as geometric optimization problems. These are combinatorial optimization problems restricted to a geometric setting, where the objective is to maximize or minimize a function of a number of variables subject to a large number of constraints induced by a given collection of geometric input objects. These include, for example, problems on geometric graphs, geometric packing and covering, robot motion planning, and geometric pattern analysis.We propose to systematically study the parameterized complexity of computationally hard (NP-hard) geometric optimization problems. So far, the main approach for dealing with such problems has been approximation algorithms. However, such algorithms often have prohibitively high running times even for small error sizes while many geometric problems have been shown to be inapproximable. Parameterized complexity on the other hand provides a framework for a more refined, `multi-dimensional' analysis of hard combinatorial problems. It measures their complexity in terms of one or more parameters in addition to the traditional input size. In concrete applications parameters are hoped to take relatively small values, resulting in practical (efficient) algorithms. Geometric problems often come with such parameters, which, in a sense, measure properties of the input objects. In this project, we would like to develop new techniques, especially by combining methods from both fields of parameterized complexity and computational geometry, and use these techniques to tackle concrete fundamental problems from various application areas, such as discrete optimization, pattern analysis, sensor networks, and art galleries.

许多现实世界的问题都可以表述为几何优化问题。这些是限制于几何设置的组合优化问题，其目标是最大化或最小化受给定几何输入对象集合引起的大量约束的许多变量的函数。例如，这些问题包括几何图形、几何填充和覆盖、机器人运动规划和几何图案分析。我们提出系统地研究计算困难（NP-hard）几何优化问题的参数化复杂性。到目前为止，处理这类问题的主要方法是近似算法。然而，这样的算法往往有过高的运行时间，即使小的误差大小，而许多几何问题已被证明是不可近似的。另一方面，参数化复杂性为复杂组合问题的更精细的“多维”分析提供了一个框架。除了传统的输入大小之外，它还根据一个或多个参数来衡量它们的复杂性。在具体应用中，希望参数取相对较小的值，从而得到实用（高效）的算法。几何问题通常伴随着这样的参数，从某种意义上说，这些参数测量了输入对象的属性。在这个项目中，我们希望开发新的技术，特别是通过结合参数化复杂性和计算几何两个领域的方法，并使用这些技术来解决来自各个应用领域的具体基本问题，如离散优化、模式分析、传感器网络和艺术画廊。

项目成果

Orthogonal Terrain Guarding is NP-complete

正交地形防护是 NP 完全的

• DOI: 10.48550/arxiv.1710.00386
• 发表时间: 2017
• 期刊: arXiv e-prints
• 作者: Bonnet

On the parameterized complexity of red-blue points separation

红蓝点分离的参数化复杂度

• DOI: 10.20382/jocg.v10i1a7
• 发表时间: 2019
• 作者: Bonnet E

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

圆盘图上最大团的 QPTAS 和次指数算法

• DOI: 10.48550/arxiv.1712.05010
• 发表时间: 2017
• 期刊: arXiv e-prints
• 作者: Bonnet

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

圆盘和单位球图上最大团的 EPTAS 和次指数算法

• DOI: 10.1145/3433160
• 发表时间: 2021
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Bonamy M