Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs
详细信息 查看全文
- 作者：Matúš Mihalák ; Rastislav Šrámek ; Peter Widmayer
- 关键词：Shortest paths ; Approximation algorithms ; Counting
- 刊名：Theory of Computing Systems
- 出版年：2016
- 出版时间：January 2016
- 年：2016
- 卷：58
- 期：1
- 页码：45-59
- 全文大小：252 KB
- 参考文献：1.Broder, A.Z., Mayr, E.W.: Counting minimum weight spanning trees. J. Algorithm. 24, 171–176 (1997)MATH MathSciNet CrossRef
2.Buhmann, J.M., Mihalák, M., Šrámek, R., Widmayer, P.: Robust optimization in the presence of uncertainty. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Sciencei (ITCS). pp. 505–514. ACM, New York (2013)
3.Burge, C., Karlin, S.: Prediction of complete gene structures in human genomic DNA. J. Mol. Biol. 268(1), 78–94 (1997)CrossRef
4.Chen, T., Kao, M.Y., Tepel, M., Rush, J., Church, G.M.: A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol. 8(3), 325–337 (2001)CrossRef
5.Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press (1998)
6.Dyer, M., Frieze, A., Kannan, R., Kapoor, A., Perkovic, L., Vazirani, U.: A mildly exponential time algorithm for approximating the number of solutions to a multidimensional knapsack problem. Comb. Probab. Comput. 2(3), 271–284 (1993)MATH MathSciNet CrossRef
7.Gopalan, P., Klivans, A., Meka, R., Štefankovič, D., Vempala, S., Vigoda, E.: An FPTAS for # knapsack and related counting problems. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). pp. 817–826 (2011)
8.Jerrum, M.: Two-dimensional monomer-dimer systems are computationally intractable. J. Stat. Phys. 48(1–2), 121–134 (1987)MathSciNet CrossRef
9.Karp, R.M.: Reducibility Among Combinatorial Problems. Springer (1972)
10.Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms: Generation, Enumeration, and Search (1998)
11.Lu, B., Chen, T.: A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol. 10(1), 1–12 (2003)CrossRef
12.Naor, D., Brutlag, D.: On suboptimal alignments of biological sequences. In: Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching (CPM). pp. 179–196. Springer (1993)
13.Rizzi, R., Tomescu, A.I.: Combinatorial decomposition approaches for efficient counting and random generation fptases. CoRR abs/1307.2347v2 (2013)
14.Štefankovič, D., Vempala, S., Vigoda, E.: A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM J. Comput. 41(2), 356–366 (2012)MATH MathSciNet CrossRef
15.Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189–201 (1979)MATH MathSciNet CrossRef
16.Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410–421 (1979)MATH MathSciNet CrossRef - 作者单位：Matúš Mihalák (1)
Rastislav Šrámek (1)
Peter Widmayer (1)
1. Institute of Theoretical Computer Science, Department of Computer Science, ETH Zurich, Switzerland - 刊物类别：Computer Science
- 刊物主题：Theory of Computation
Computational Mathematics and Numerical Analysis - 出版者：Springer New York
- ISSN：1433-0490
文摘
Given a directed acyclic graph with non-negative edge-weights, two vertices s and t, and a threshold-weight L, we present a fully-polynomial time approximation-scheme for the problem of counting the s-t paths of length at most L. This is best possible, as we also show that the problem is #P-complete. We then show that, unless P=NP, there is no finite approximation to the bi-criteria version of the problem: count the number of s-t paths of length at most L 1 in the first criterion, and of length at most L 2 in the second criterion. On the positive side, we extend the approximation scheme for the relaxed version of the problem, where, given thresholds L 1 and L 2, we relax the requirement of the s-t paths to have length exactly at most L 1, and allow the paths to have length at most L 1′ : = (1+δ)L 1, for any δ > 0.