地基设置成本预算的最大覆盖率问题
Irving van Heuven van Staereling1, Bart de Keijzer2, Guido Schäfer1,3
1Networks & Optimization Group, Centrum Wiskunde & Informatica, Science Park 123, Amsterdam, 1098 XG The Netherlands.
Theory of computing systems
|November 24, 2025
概括
本研究介绍了一个预算的最大覆盖范围的变种,用于优化投标. 研究人员开发了近似算法,包括针对特定超图结构的全多项式时间近似方案.
科学领域:
- 组合优化的优化.
- 算法设计 算法设计
- 计算复杂性 计算复杂性
背景情况:
- 预算的最大覆盖率问题是各种领域的应用程序的一个基本的NP-hard问题.
- 引入了一个自然变体,在预算限制范围内考虑顶点成本,而不是超边缘成本.
- 这个问题是由赞助搜索拍卖中的应用引起的,特别是竞价优化.
研究的目的:
- 调查预算最大覆盖率问题与顶点成本的新变体.
- 为这个问题开发高效的近似算法.
- 分析问题的近似性,并确定准确或近乎准确的解决方案的条件.
主要方法:
- 该研究采用了近似算法和复杂性理论的技术.
- 从众所周知的硬问题 (如密度最大的k-subgraph) 进行减小,以确定不可接近性结果.
- 针对不同类型的超图,开发了特定的算法方法,包括贪策略和动态编程.
主要成果:
- 这个问题被证明至少和标准预算的最大覆盖率问题一样困难,这意味着[公式:参见文本]-不可接近性.
- 一个[公式:见文本]-近似算法是为一般图表.
- 一个完全多项式时间近似方案 (FPTAS) 对于高图,其发生率图是森林 (Berge-acyclic) 衍生,具有固定反集的扩展.
- 一个[公式:见文本]-近似算法为基于最大顶点度的一般超图提供.
结论:
- 开发的算法为预算最大覆盖率问题的特定实例提供了显著的改进.
- 这些发现提供了对问题的复杂性及其对优化投标的实际影响的理论理解.
- 未来的工作可以探索这些算法技术的进一步扩展和应用.
相关概念视频
01:17Design Example: Analyzing Capacity Contours for Flood Risk Assessment
270
Flood risk assessment involves careful planning and analysis to ensure the safety of communities near water retention structures. Capacity contours are a vital tool in this process, as they illustrate the potential spread of water at specific levels in a given area. In the context of building a bund across a small valley, these contours play a critical role in evaluating the safety of nearby residential areas.In this example, the bund is intended to store stormwater in the valley. The engineers...
270
01:05Estimation of the Physical Quantities
7.2K
On many occasions, physicists, other scientists, and engineers need to make estimates of a particular quantity. These are sometimes referred to as guesstimates, order-of-magnitude approximations, back-of-the-envelope calculations, or Fermi calculations. The physicist Enrico Fermi was famous for his ability to estimate various kinds of data with surprising precision. Estimating does not mean guessing a number or a formula at random. Instead, estimation means using prior experience and sound...
7.2K
01:17Design Example: Alignment of a Road Line Using GIS
317
The alignment of a road line using Geographic Information Systems (GIS) is a critical process in civil engineering, combining advanced technology with practical decision-making. This methodology begins with the collection of geospatial data, including information on land cover, geomorphology, drainage patterns, slope, and contour details. Such data is typically acquired through satellite imagery and GIS tools, offering a comprehensive understanding of the terrain.Once the data is gathered, it...
317
01:20Maxwell-Boltzmann Distribution: Problem Solving
2.8K
Individual molecules in a gas move in random directions, but a gas containing numerous molecules has a predictable distribution of molecular speeds, which is known as the Maxwell-Boltzmann distribution, f(v).
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
2.8K
01:09Radiation Pressure: Problem Solving
774
The radiation pressure applied by an electromagnetic wave on a perfectly absorbing surface equals the energy density of the wave. The wave's momentum also gets transferred to the surface when an electromagnetic wave is entirely absorbed by it. The rate at which momentum is transmitted to an absorbing surface perpendicular to the propagation direction equals the force on the surface.
The average value of the rate of momentum transfer divided by the absorbing area represents the average force...
The average value of the rate of momentum transfer divided by the absorbing area represents the average force...
774
01:12Taping Over Different Ground Profiles
317
Taping over varying ground profiles requires careful adaptation to achieve accurate measurements. On smooth, level ground with minimal vegetation, the tape can rest directly on the ground. Here, the taping team, typically consisting of a head and a rear tapeman, coordinates their positions with clear communication. The rear tapeman holds the tape at the starting point and guides the head tapeman toward a range pole placed beyond the endpoint, using hand or voice signals to ensure alignment.On...
317