Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRed-Blue-Partitioned MST, TSP, and Matching
88
0
0.0
(
0
)
Added by
Matthew Johnson
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Matthew P. Johnson
Ask ChatGPT about the research
No Arabic abstract
Arkin et al.~cite{ArkinBCCJKMM17} recently introduced textit{partitioned pairs} network optimization problems: given a metric-weighted graph on $n$ pairs of nodes, the task is to color one node from each pair red and the other blue, and then to compute two separate textit{network structures} or disjoint (node-covering) subgraphs of a specified sort, one on the graph induced by the red nodes and the other on the blue nodes. Three structures have been investigated by cite{ArkinBCCJKMM17}---textit{spanning trees}, textit{traveling salesperson tours}, and textit{perfect matchings}---and the three objectives to optimize for when computing such pairs of structures: textit{min-sum}, textit{min-max}, and textit{bottleneck}. We provide improved approximation guarantees and/or strengthened hardness results for these nine NP-hard problem settings.
rate research
Read More
Given a set R of red points and a set B of blue points in the plane, the Red-Blue point separation problem asks if there are at most k lines that separate R from B, that is, each cell induced by the lines of the solution is either empty or monochromatic (containing points of only one color). A common variant of the problem is when the lines are required to be axis-parallel. The problem is known to be NP-complete for both scenarios, and W[1]-hard parameterized by k in the former setting and FPT in the latter. We demonstrate a polynomial-time algorithm for the special case when the points lie on a circle. Further, we also demonstrate the W-hardness of a related problem in the axis-parallel setting, where the question is if there are p horizontal and q vertical lines that separate R from B. The hardness here is shown in the parameter p.
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solutions cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.
Given a metric $(V,d)$ and a $textsf{root} in V$, the classic $textsf{$k$-TSP}$ problem is to find a tour originating at the $textsf{root}$ of minimum length that visits at least $k$ nodes in $V$. In this work, motivated by applications where the input to an optimization problem is uncertain, we study two stochast
Bloom filters (BF) are widely used for approximate membership queries over a set of elements. BF variants allow removals, sets of unbounded size or querying a sliding window over an unbounded stream. However, for this last case the best current approaches are dictionary based (e.g., based on Cuckoo Filters or TinyTable), and it may seem that BF-based approaches will never be competitive to dictionary-based ones. In this paper we present Age-Partitioned Bloom Filters, a BF-based approach for duplicate detection in sliding windows that not only is competitive in time-complexity, but has better space usage than current dictionary-based approaches (e.g., SWAMP), at the cost of some moderate slack. APBFs retain the BF simplicity, unlike dictionary-based approaches, important for hardware-based implementations, and can integrate known improvements such as double hashing or blocking. We present an Age-Partitioned Blocked Bloom Filter variant which can operate with 2-3 cache-line accesses per insertion and around 2-4 per query, even for high accuracy filters.
We consider the problem of designing sublinear time algorithms for estimating the cost of a minimum metric traveling salesman (TSP) tour. Specifically, given access to a $n times n$ distance matrix $D$ that specifies pairwise distances between $n$ points, the goal is to estimate the TSP cost by performing only sublinear (in the size of $D$) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any $varepsilon > 0$, there exists an $tilde{O}(n/varepsilon^{O(1)})$ time algorithm that returns a $(1 + varepsilon)$-approximate estimate of the MST cost. This result immediately implies an $tilde{O}(n/varepsilon^{O(1)})$ time algorithm to estimate the TSP cost to within a $(2 + varepsilon)$ factor for any $varepsilon > 0$. However, no $o(n^2)$ time algorithms are known to approximate metric TSP to a factor that is strictly better than $2$. On the other hand, there were also no known barriers that rule out the existence of $(1 + varepsilon)$-approximate estimation algorithms for metric TSP with $tilde{O}(n)$ time for any fixed $varepsilon > 0$. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. We also show that the problem of estimating metric TSP cost is closely connected to the problem of estimating the size of a maximum matching in a graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
