首页    期刊浏览 2024年07月18日 星期四
登录注册

文章基本信息

  • 标题:Near-Linear Time Algorithm for n-fold ILPs via Color Coding
  • 本地全文:下载
  • 作者:Klaus Jansen ; Alexandra Lassota ; Lars Rohwedder
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:132
  • 页码:1-13
  • DOI:10.4230/LIPIcs.ICALP.2019.75
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study an important case of ILPs max {c^Tx Ax = b, l <= x <= u, x in Z^{n t}} with n * t variables and lower and upper bounds l, u in Z^{nt}. In n-fold ILPs non-zero entries only appear in the first r rows of the matrix A and in small blocks of size s x t along the diagonal underneath. Despite this restriction many optimization problems can be expressed in this form. It is known that n-fold ILPs can be solved in FPT time regarding the parameters s, r, and Delta, where Delta is the greatest absolute value of an entry in A. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction. Both, the number of iterations and the search for such an improving direction take time Omega(n), leading to a quadratic running time in n. We introduce a technique based on Color Coding, which allows us to compute these improving directions in logarithmic time after a single initialization step. This leads to the first algorithm for n-fold ILPs with a running time that is near-linear in the number nt of variables, namely (rs Delta)^{O(r^2s + s^2)} L^2 * nt log^{O(1)}(nt), where L is the encoding length of the largest integer in the input. In contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead, we give a structural lemma to introduce appropriate bounds. If, on the other hand, we are given such an LP solution, the running time can be decreased by a factor of L.
  • 关键词:Near-Linear Time Algorithm; n-fold ILP; Color Coding
国家哲学社会科学文献中心版权所有