整数流量分配问题:对随机图的算法和见解
Rayan Harfouche1, Giovanni Piccioli1, Lenka Zdeborová1
1École Polytechnique Fédérale de Lausanne (EPFL), Statistical Physics of Computation Laboratory.
Physical review. E
|February 20, 2025
概括
本研究介绍了整数流量分配问题 (ITAP) 的算法,这是一个复杂的路由挑战. 消息传递和模拟化在有吸引力的场景中表现出色,优于简单的方法.
科学领域:
- 运营研究 运营研究
- 计算机科学 计算机科学
- 网络优化 网络优化
背景情况:
- 路径优化对于交通和数据路由等现实世界系统至关重要.
- 流量分配问题 (TAP) 是一个连续优化问题.
- 整数流量分配问题 (ITAP) 是TAP的一个离散的NP硬变体.
研究的目的:
- 开发和评估用于解决整数流量分配问题 (ITAP) 的算法.
- 探索排斥性 (尽量减少拥堵) 和有吸引力的 (尽量减少边缘使用) 交互场景.
- 分析TAP和ITAP之间的关系和趋同.
主要方法:
- 实现并比较了四个算法:消息传递,贪的方法,模拟和放松与TAP.
- 在大型稀疏随机正规图上进行实验,随机出发目的地对.
- 研究了TAP和ITAP解决方案之间的扩展制度和趋同率.
主要成果:
- 贪的算法在令人厌恶的场景中具有竞争力.
- 在有吸引力的场景中,消息传递和模拟回火显示出卓越的性能.
- 随着路径数量的增加,TAP的解决方案汇聚到ITAP,并确定了扩展模式.
结论:
- 不同的算法对ITAP是有效的,取决于相互作用类型 (排斥性与吸引性).
- 连续TAP在特定条件下 (大量路径) 提供了与ITAP的近似.
- 了解TAP-ITAP关系是有效优化网络流量的关键.
相关概念视频
Group Design
8.8K
The most basic experimental design involves two groups: the experimental group and the control group. The two groups are designed to be the same except for one difference— experimental manipulation. The experimental group gets the experimental manipulation—that is, the treatment or variable being tested—and the control group does not. Since experimental manipulation is the only difference between the experimental and control groups, we can be sure that any differences between...
8.8K
Randomized Experiments
6.6K
The randomization process involves assigning study participants randomly to experimental or control groups based on their probability of being equally assigned. Randomization is meant to eliminate selection bias and balance known and unknown confounding factors so that the control group is similar to the treatment group as much as possible. A computer program and a random number generator can be used to assign participants to groups in a way that minimizes bias.
Simple randomization
Simple...
Simple randomization
Simple...
6.6K
Probability Distributions
6.5K
The probability of a random variable x is the likelihood of its occurrence. A probability distribution represents the probabilities of a random variable using a formula, graph, or table. There are two types of probability distribution– discrete probability distribution and continuous probability distribution.
A discrete probability distribution is a probability distribution of discrete random variables. It can be categorized into binomial probability distribution and Poisson...
A discrete probability distribution is a probability distribution of discrete random variables. It can be categorized into binomial probability distribution and Poisson...
6.5K
Probability Histograms
10.9K
A probability histogram is a visual representation of a probability distribution. Similar a typical histogram, the probability histogram consists of contiguous (adjoining) boxes. It has both a horizontal axis and a vertical axis. The horizontal axis is labeled with what the data represents. The vertical axis is labeled with probability. Each rectangular bar in the histogram is 1 unit wide, which suggests that the area under each bar equals the probability, P(x), where x is 1, 2, 3, and so on.
10.9K
Distributed Loads: Problem Solving
590
Beams are structural elements commonly employed in engineering applications requiring different load-carrying capacities. The first step in analyzing a beam under a distributed load is to simplify the problem by dividing the load into smaller regions, which allows one to consider each region separately and calculate the magnitude of the equivalent resultant load acting on each portion of the beam. The magnitude of the equivalent resultant load for each region can be determined by calculating...
590
Random Variables
11.2K
A random variable is a single numerical value that indicates the outcome of a procedure. The concept of random variables is fundamental to the probability theory and was introduced by a Russian mathematician, Pafnuty Chebyshev, in the mid-nineteenth century.
Uppercase letters such as X or Y denote a random variable. Lowercase letters like x or y denote the value of a random variable. If X is a random variable, then X is written in words, and x is given as a number.
For example, let X = the...
Uppercase letters such as X or Y denote a random variable. Lowercase letters like x or y denote the value of a random variable. If X is a random variable, then X is written in words, and x is given as a number.
For example, let X = the...
11.2K


