4 citations · 4 across the 4 of their papers we have counts for
4 papers
On joint triangulations of two sets of points in the plane
Ajit Arvind Diwan, Subir Kumar Ghosh, Partha Pratim Goswami +1
In this paper, we establish two necessary conditions for a joint triangulation of two sets of points in the plane and conjecture that they are sufficient. We show that these ne…
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…
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications
Piotr Berman, Marek Karpinski, Andrzej Lingas
First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time e…