...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Multistage Matchings
【24h】

Multistage Matchings

机译：多阶段匹配

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider a multistage version of the Perfect Matching problem which models the scenario where the costs of edges change over time and we seek to obtain a solution that achieves low total cost, while minimizing the number of changes from one instance to the next. Formally, we are given a sequence of edge-weighted graphs on the same set of vertices V, and are asked to produce a perfect matching in each instance so that the total edge cost plus the transition cost (the cost of exchanging edges), is minimized. This model was introduced by Gupta et al. (ICALP 2014), who posed as an open problem its approximability for bipartite instances. We completely resolve this question by showing that Minimum Multistage Perfect Matching (Min-MPM) does not admit an n^{1-epsilon}-approximation, even on bipartite instances with only two time steps.Motivated by this negative result, we go on to consider two variations of the problem. In Metric Minimum Multistage Perfect Matching problem (Metric-Min-MPM) we are promised that edge weights in each time step satisfy the triangle inequality. We show that this problem admits a 3-approximation when the number of time steps is 2 or 3. On the other hand, we show that even the metric case is APX-hard already for 2 time steps. We then consider the complementary maximization version of the problem, Maximum Multistage Perfect Matching problem (Max-MPM), where we seek to maximize the total profit of all selected edges plus the total number of non-exchanged edges. We show that Max-MPM is also APX-hard, but admits a constant factor approximation algorithm for any number of time steps.
机译：我们考虑完美匹配问题的多阶段版本，该版本对边的成本随时间变化的情况进行建模，我们寻求获得一种实现总成本较低的解决方案，同时最大程度地减少从一个实例到下一个实例的更改次数。形式上，我们在同一组顶点V上获得了一系列边缘加权图，并要求它们在每种情况下产生完美匹配，以便总边缘成本加上过渡成本（交换边缘的成本）为最小化。该模型由Gupta等人介绍。 （ICALP 2014），他提出了一个开放性问题，即二分实例的近似性。我们通过证明最小多级完美匹配（Min-MPM）甚至在只有两个时间步长的二分实例上也不允许n ^ {1-epsilon}逼近来完全解决了这个问题。考虑问题的两个变体。在度量最小多级完美匹配问题（Metric-Min-MPM）中，我们保证每个时间步的边缘权重都满足三角形不等式。我们证明，当时间步长为2或3时，此问题允许3逼近。另一方面，我们证明，即使度量标准的情况对于2个时间步长也已达到APX严格标准。然后，我们考虑问题的互补最大化版本，即最大多阶段完美匹配问题（Max-MPM），我们在此寻求最大化所有选定边的总利润加上未交换边的总数。我们证明Max-MPM也是APX硬性的，但是对于任何数量的时间步长都可以采用恒定因子近似算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号