4 citations · 5 across the 6 of their papers we have counts for
4 papers · 1 filter
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact comple…
Optimal Cuts and Bisections on the Real Line in Polynomial Time
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
The exact complexity of geometric cuts and bisections is the longstanding open problem including even the dimension one. In this paper, we resolve this problem for dimension one (t…
Near approximation of maximum weight matching through efficient weight reduction
Andrzej Lingas, Cui Di
Let G be an edge-weighted hypergraph on n vertices, m edges of size \le s, where the edges have real weights in an interval [1,W]. We show that if we can approximate a maximum weig…
PTAS for k-tour cover problem on the plane for moderately large values of k
Anna Adamaszek, Artur Czumaj, Andrzej Lingas
Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem…