发帖
雷达卡
摘要翻译：
本文引用{hatfimmokomi11}和{azizbrilharr13}提出了检验由一个在宇宙$u$上的长度$n$的（严格）偏好列表所诱导的选择函数是否可替换的算法。这些算法的运行时间分别为$O(U^3\CDOT N^3)$和$O(U^2\CDOT N^3)$。在本文中，我们给出了一个运行时间$O(u^2\cdot n^2)$的算法。注意$N$可能是宇宙的尺寸$U$的指数。
---
英文标题：
《On testing substitutability》
---
作者：
Cosmina Croitoru, Kurt Mehlhorn
---
最新提交年份：
2018
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Data Structures and Algorithms 数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Economics 经济学
二级分类：Econometrics 计量经济学
分类描述：Econometric Theory, Micro-Econometrics, Macro-Econometrics, Empirical Content of Economic Relations discovered via New Methods, Methodological Aspects of the Application of Statistical Inference to Economic Data.
计量经济学理论，微观计量经济学，宏观计量经济学，通过新方法发现的经济关系的实证内容，统计推论应用于经济数据的方法论方面。
--
---
英文摘要：
The papers~\cite{hatfimmokomi11} and~\cite{azizbrilharr13} propose algorithms for testing whether the choice function induced by a (strict) preference list of length $N$ over a universe $U$ is substitutable. The running time of these algorithms is $O(|U|^3\cdot N^3)$, respectively $O(|U|^2\cdot N^3)$. In this note we present an algorithm with running time $O(|U|^2\cdot N^2)$. Note that $N$ may be exponential in the size $|U|$ of the universe.
---
PDF链接：
https://arxiv.org/pdf/1805.07642
京公网安备 11010802022788号
