ineptitude
发表于 2025-3-23 13:30:19
Inapproximability of Survivable Networksreserving reduction from . to .. Our reduction extends and widely generalizes as well as significantly simplifies the main results of . Using it, we derive some new hardness of approximation results, as follows. We show that directed and undirected variants of . and of .. are equivalent w.r.t. ap
muffler
发表于 2025-3-23 17:30:47
http://reply.papertrans.cn/17/1605/160455/160455_12.png
不怕任性
发表于 2025-3-23 18:11:38
http://reply.papertrans.cn/17/1605/160455/160455_13.png
organic-matrix
发表于 2025-3-24 00:32:08
http://reply.papertrans.cn/17/1605/160455/160455_14.png
vanquish
发表于 2025-3-24 04:12:17
The Directed Minimum Latency Problemtencies at all vertices (the latency of any vertex . ∈ . is the distance from . to . along the path). This problem has been well-studied on symmetric metrics, and the best known approximation guarantee is 3.59 . For any ., we give an .. time algorithm for directed latency that achieves an approxi
Inordinate
发表于 2025-3-24 07:16:15
A Simple LP Relaxation for the Asymmetric Traveling Salesman Problemman Problem (ATSP) is a constant. In this paper, we give a simpler LP relaxation for the ASTP. The integrality gaps of this relaxation and of the Held-Karp relaxation are within a constant factor of each other. Our LP is simpler in the sense that its extreme solutions have at most 2. − 2 non-zero va
enmesh
发表于 2025-3-24 12:00:12
Approximating Directed Weighted-Degree Constrained Networkslems that seek to find a minimum cost . graph that satisfies both . connectivity requirements and . constraints. The input to such problems is a directed graph . = (.,.), edge-costs {.(.):. ∈ .}, edge-weights {.(.):. ∈ .}, an intersecting supermodular set-function . on ., and degree bounds {.(.):. ∈
并入
发表于 2025-3-24 15:52:21
http://reply.papertrans.cn/17/1605/160455/160455_18.png
我的巨大
发表于 2025-3-24 19:50:19
Deterministic 7/8-Approximation for the Metric Maximum TSPThis improves over both the randomized algorithm of Hassin and Rubinstein with expected approximation ratio of 7/8 − .(..) and the deterministic (7/8 − .(..))-approximation algorithm of Chen and Nagoya ..In the new algorithm, we extend the approach of processing local configurations using so-called loose-ends, which we introduced in .
Nucleate
发表于 2025-3-25 01:15:13
Springer Tracts in Modern Physics 21tems . = (.., ..., ..). The goal is to output a binary tree where each internal node is a test, each leaf is an item and the total external path length of the tree is minimized. Total external path length is the sum of the depths of all the leaves in the tree. DT has a long history in computer scien