谦卑
发表于 2025-3-28 15:33:12
Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs and bin packing. Given the hardness of the problems, we study polynomial-time approxi- mation algorithms with bounded performance guarantees. We introduce techniques which yield new algorithms for a wide range of disjoint-path problems. We use two basic techniques. First, we propose simple greedy a
flutter
发表于 2025-3-28 21:19:49
Approximation Algorithms for the Mixed Postman Problemed graph (a graph containing both undirected and directed edges) at least once. The problem is solvable in polynomial time either if the graph is undirected or if the graph is directed, but NP-hard in mixed graphs. An approximation algorithm with a performance ratio of 3/2 for the postman problem on
建筑师
发表于 2025-3-28 23:40:34
http://reply.papertrans.cn/47/4683/468250/468250_43.png
详细目录
发表于 2025-3-29 03:49:45
The Maximum Traveling Salesman Problem Under Polyhedral Norms. We show that for any such norm, the problem of finding a tour of . length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time .(.. log .), where . is the number of facets of the polyhedron determining the polyhedral norm. Thus for ex
comely
发表于 2025-3-29 11:07:23
Polyhedral Combinatorics of Benzenoid Problemsthe molecules. Hansen and Zheng (1994) formulated this problem as an integer program and conjectured, based on computational evidence, that solving the linear programming relaxation always yields integral solutions. We establish their conjecture by showing that the constraint matrices of these probl
走调
发表于 2025-3-29 13:11:53
Consecutive Ones and a Betweenness Problem in Computational Biologyorates the solution of consecutive ones problems and show that it supersedes an earlier one. A particular feature of this new branch-and-cut algorithm is that it is not based on an explicit integer programming formulation of the problem and makes use of automatically generated facet-defining inequal
牛马之尿
发表于 2025-3-29 16:36:27
http://reply.papertrans.cn/47/4683/468250/468250_47.png
不真
发表于 2025-3-29 23:05:54
http://reply.papertrans.cn/47/4683/468250/468250_48.png
brachial-plexus
发表于 2025-3-30 00:48:51
http://reply.papertrans.cn/47/4683/468250/468250_49.png
能量守恒
发表于 2025-3-30 05:07:27
An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphshat has the minimum number of edges. The best previous approximation guarantee was .. If the well known TSP . conjecture holds, then there is a .-approximation algorithm. Thus our main result gets half-way to this target.