二元容量公共整数多拟阵基的FPRAS
An FPRAS for Common Integer Polymatroid Bases with Binary Capacities
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究计数两个总秩相同的多拟阵的公共整数基问题。摘要表示，作者在给定精确秩值预言机下给出完全多项式随机近似方案（FPRAS），总秩与容量以二进制编码，每个整数向量只计一次。每次执行时，预言机调用次数及预言机之外的位运算量由基集大小、二进制输入长度、相对误差倒数与失败概率倒数的对数所构成的固定多项式界定。算法直接处理二进制容量，无需展开为带标签副本。手稿尚未经独立审查或同行评议。
- 为两个同总秩多拟阵的公共整数基计数给出FPRAS。
- 容量以二进制编码，算法不展开为带标签副本。
- 复杂度由基集大小、输入长度与误差参数的多项式界定。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We give a fully polynomial randomized approximation scheme for counting common integer bases of two polymatroids with the same total rank, supplied by exact rank-value oracles. The total rank and capacities are encoded in binary, and each integer vector is counted once. On every execution, the number of oracle calls and the bit work outside the oracles are bounded by a fixed polynomial in the ground-set size, the binary input length, the inverse relative-error tolerance, and the logarithm of the inverse failure probability. The algorithm handles binary capacities directly, without expanding them into labelled copies.
用户标记：未标记
固定编号：f669925381b5e104
原文来源