在对象对象的相关差距上的差距
Edin Husić1, Zhuan Khye Koh2, Georg Loho3
1IDSIA, USI-SUPSI, Lugano, Switzerland.
概括
我们介绍了对matroid等级函数的相关性差距的细粒度分析,根据matroid等级和周长提供了改进的下界. 这项研究增强了对近似算法和机制设计的理解.
科学领域:
- 离散数学 离散数学 离散数学
- 理论计算机科学 理论计算机科学
- 运营研究 运营研究
背景情况:
- 相关差距量化了集合函数的两个扩展到单位立方体之间的比.
- 它在近似算法和机制设计中作为性能保证.
- 现有的研究表明,单调的亚模块函数的相关性差距至少为1/e,简单的matroid等级函数的紧张性.
研究的目的:
- 为了对相关性差距进行细粒度的研究,特别针对matroid等级函数.
- 为了获得相关性差距的改进下限.
- 为了研究母体性质对相关性差距的影响.
主要方法:
- 分析matroid等级函数的相关性差距.
- 开发新的下界参数由matroid等级和 girth.
- 在加权等级函数下调查相关差距的行为.
主要成果:
- 一个改进的下界对matroid等级函数的相关性差距,取决于等级和周长.
- 证明 matroid 的加权等级函数的相关性差距在均权重的情况下被最小化.
- 建立具有直接算法影响的新理论界限.
结论:
- 这项研究提供了更细致的了解对 matroids 的相关性差距.
- 这些发现为相关的优化问题提供了更严格的性能保证.
- 这项研究推进了子模块最大化,机制设计和争议解决领域.
相关概念视频
Correlations
32.4K
Correlation means that there is a relationship between two or more variables (such as ice cream consumption and crime), but this relationship does not necessarily imply cause and effect. When two variables are correlated, it simply means that as one variable changes, so does the other. We can measure correlation by calculating a statistic known as a correlation coefficient. A correlation coefficient is a number from -1 to +1 that indicates the strength and direction of the relationship between...
32.4K
Routh-Hurwitz Criterion II
170
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
170
Routh-Hurwitz Criterion I
134
Consider an electrical power grid, where stability is essential to prevent blackouts. The Routh-Hurwitz criterion is a valuable tool for assessing system stability under varying load conditions or faults. By analyzing the closed-loop transfer function, the Routh-Hurwitz criterion helps determine whether the system remains stable.
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
134
Coefficient of Correlation
6.0K
The correlation coefficient, r, developed by Karl Pearson in the early 1900s, is numerical and provides a measure of strength and direction of the linear association between the independent variable x and the dependent variable y.
If you suspect a linear relationship between x and y, then r can measure how strong the linear relationship is.
What the VALUE of r tells us:
The value of r is always between –1 and +1: –1 ≤ r ≤ 1.
The size of the correlation r indicates the...
If you suspect a linear relationship between x and y, then r can measure how strong the linear relationship is.
What the VALUE of r tells us:
The value of r is always between –1 and +1: –1 ≤ r ≤ 1.
The size of the correlation r indicates the...
6.0K
Relation between Mathematical Equations and Block Diagrams
159
In a spring-mass-damper system, the second-order differential equation describes the dynamic behavior of the system. When transformed into the Laplace domain under zero initial conditions, this equation can be effectively analyzed and manipulated. The transformation into the Laplace domain converts differential equations into algebraic equations, simplifying the process of isolating the output.
159
Correlation
11.5K
In statistics, two variables are said to be correlated if the values of one variable are associated with the other variable. Depending on the relationship between two variables, correlation can be of three types– positive correlation, negative correlation, and zero correlation.
Two variables, for example, a and b, are said to be positively correlated if both variables move in the same direction. In other words, a positive correlation exists between two variables, a and b, if:
Two variables, for example, a and b, are said to be positively correlated if both variables move in the same direction. In other words, a positive correlation exists between two variables, a and b, if:
11.5K


