在线计算中的几个未解问题(英文)

讨论组合优化中的一个迅速发展的领域──在线计算，选出几个典型的未解问题进行方法介绍．     

摩擦市场的利率期限结构的无套利分析

本文用无套利方法分析有摩擦金融市场中利率的期限结构.对存在有限个债券和离散有限个到期日以及存在成比例的交易费、买卖差价、税赋这三种摩擦的金融市场,引入了相容期限结构的概念,给出了相容期限结构和套利机会的存在性结果或充要条件及它们的识别与计算方法.     

二部图中求正交于星的(g, f)-染色的一个多项式算法

令G是一个具有顶点集V(G)和边集 E(G)的二部图, 且令g和f是定义在 V(G)上的两个非负整数值函数,使得对每个顶点x∈V(G)都有g(x)≤f(x). G的一个(g,f)-染色是一个推广的边染色,它满足在每个顶点x每一种颜色至少出现g(x)次且至多出现f(x)次. 给出了求二部图中满足某些约束条件且具有最小颜色数的(g,f)-染色的一个多项式算法并证明了此结果是最好的可能.     

拍卖机制设计在区块链中的应用与挑战

区块链是新一代信息技术的重要组成部分,是分布式网络、加密技术、智能合约等多种技术集成的新型数据库软件。过去的十多年,区块链技术在全球范围内产生广泛影响。如今的区块链技术,已从最初的关注于解决货币和支付的去中心化问题,转入到解决市场的去中心化问题。智能合约的出现使得基于区块链技术的去中心化金融进入高速发展状态,也涌现出区块链环境下的各类拍卖场景。本文首次从机制设计角度,以区块链交易费机制,非同质化代币(Non-Fungible Token,NFT)拍卖和矿工可提取价值(Miner-Extractable Value,MEV)交易位置拍卖为主要对象,总结和剖析近些年来区块链上特有的拍卖机制;并针对区块链特性,提出区块链上拍卖机制设计所面临的挑战和未来亟待解决的问题。     

系列平行图的除V*外的边覆盖划分

任意给定系列平行图G的一个顶点v^*, 则G的边集可划分为k=min {κ′(G)+1, δ(G)}个子集, 使得每一个边子集覆盖可能除v^*以外的所有顶点, 其中δ(G)为G的最小度, κ′(G)为G的边连通度. 另外, 证明了该结果是最好的可能, 并且通过此证明过程得到一个可找到该划分的多项式时间算法.