Recent zbMATH articles in MSC 68W25https://zbmath.org/atom/cc/68W252021-06-15T18:09:00+00:00WerkzeugEfficient approximation for restricted biclique cover problems.https://zbmath.org/1460.051542021-06-15T18:09:00+00:00"Epasto, Alessandro"https://zbmath.org/authors/?q=ai:epasto.alessandro"Upfal, Eli"https://zbmath.org/authors/?q=ai:upfal.eliSummary: Covering the edges of a bipartite graph by a minimum set of bipartite complete graphs (bicliques) is a basic graph theoretic problem, with numerous applications. In particular, it is used to characterize parsimonious models of a set of observations (each biclique corresponds to a factor or feature that relates the observations in the two sets of nodes connected by the biclique). The decision version of the minimum biclique cover problem is NP-Complete, and unless P = NP, the cover size cannot be approximated in general within less than a sub-linear factor of the number of nodes (or edges) in the graph. In this work, we consider two natural restrictions to the problem, motivated by practical applications. In the first case, we restrict the number of bicliques a node can belong to. We show that when this number is at least 5, the problem is still NP-hard. In contrast, we show that when nodes belong to no more than two bicliques, the problem has efficient approximations. The second model we consider corresponds to observing a set of independent samples from an unknown model, governed by a possibly large number of factors. The model is defined by a bipartite graph \(G=(L,R,E)\), where each node in \(L\) is assigned to an arbitrary subset of up to a constant \(f\) factors, while the nodes in \(R\) (the independent observations) are assigned to random subsets of the set of \(k\) factors where \(k\) can grow with size of the graph. We show that this practical version of the biclique cover problem is amenable to efficient approximations.A unified model and algorithms for temporal map labeling.https://zbmath.org/1460.681232021-06-15T18:09:00+00:00"Gemsa, Andreas"https://zbmath.org/authors/?q=ai:gemsa.andreas"Niedermann, Benjamin"https://zbmath.org/authors/?q=ai:niedermann.benjamin"NĂ¶llenburg, Martin"https://zbmath.org/authors/?q=ai:nollenburg.martinSummary: We consider map labeling for the case that a map undergoes a sequence of operations such as rotation, zoom and translation over a specified time span. We unify and generalize several previous models for dynamic map labeling into one versatile and flexible model. In contrast to previous research, we completely abstract from the particular operations and express the labeling problem as a set of time intervals representing the labels' presences, activities and conflicts. One of the model's strength is manifested in its simplicity and broad range of applications. In particular, it supports label selection both for map features with fixed position as well as for moving entities (e.g., for tracking vehicles in logistics or air traffic control). We study the active range maximization problem in this model. We prove that the problem is NP-complete and W[1]-hard, and present constant-factor approximation algorithms. In the restricted, yet practically relevant case that no more than \(k\) labels can be active at any time, we give polynomial-time algorithms as well as constant-factor approximation algorithms.Uniformity of point samples in metric spaces using gap ratio.https://zbmath.org/1460.680782021-06-15T18:09:00+00:00"Bishnu, Arijit"https://zbmath.org/authors/?q=ai:bishnu.arijit"Desai, Sameer"https://zbmath.org/authors/?q=ai:desai.sameer"Ghosh, Arijit"https://zbmath.org/authors/?q=ai:ghosh.arijit"Goswami, Mayank"https://zbmath.org/authors/?q=ai:goswami.mayank"Paul, Subhabrata"https://zbmath.org/authors/?q=ai:paul.subhabrataSummary: \textit{S. Teramoto} et al. [``Inserting points uniformly at every instance'', IEICE Trans. Inf. Syst. E89-D, No. 8, 2348--2356 (2006; \url{doi:10.1093/ietisy/e89-d.8.2348})]
defined a new measure called the \textit{gap ratio} that measures the uniformity of a finite point set sampled from \(\mathcal S\), a bounded subset of \(\mathbb {R}^2\). We attempt to generalize the definition of this measure over all metric spaces. We solve optimization related questions about selecting uniform point samples from metric spaces; the uniformity is measured using gap ratio. We give lower bounds for specific metric spaces, prove hardness and approximation hardness results. We also give a general approximation algorithm framework giving different approximation ratios for different metric spaces and give a \(\left( 1+\epsilon \right) \)-approximation algorithm for a set of points in a Euclidean space.
For the entire collection see [Zbl 1320.68020].Approximating Steiner trees and forests with minimum number of Steiner points.https://zbmath.org/1460.680732021-06-15T18:09:00+00:00"Cohen, Nachshon"https://zbmath.org/authors/?q=ai:cohen.nachshon"Nutov, Zeev"https://zbmath.org/authors/?q=ai:nutov.zeevSummary: Let \(R\) be a finite set of terminals in a metric space \((M,d)\). We consider finding a minimum size set \(S \subseteq M\) of additional points such that the unit-disc graph \(G[R \cup S]\) of \(R \cup S\) satisfies some connectivity properties. In the {\textsf {Steiner Tree with Minimum Number of Steiner Points}} ({\textsf{ST-MSP}}) problem \(G[R \cup S]\) should be connected. In the more general {\textsf {Steiner Forest with Minimum Number of Steiner Points}} ({\textsf{SF-MSP}}) problem we are given a set \(D \subseteq R {\times} R\) of demand pairs and \(G[R \cup S]\) should contains a \(uv\)-path for every \(uv \in D\). Let \(\varDelta \) be the maximum number of points in a unit ball such that the distance between any two of them is larger than 1. It is known that \(\varDelta =5\) in \(\mathbb {R}^2\). The previous known approximation ratio for {\textsf {ST-MSP}} was \(\lfloor (\varDelta +1)/2 \rfloor +1+\epsilon \) in an arbitrary normed space
[\textit{Z. Nutov} and \textit{A. Yaroshevitch}, Inf. Process. Lett. 109, No. 19, 1136--1140 (2009; Zbl 1206.68040)],
and \(2.5+\epsilon \) in the Euclidean space \(\mathbb {R}^2\)
[\textit{X. Cheng} et al., ``Relay sensor placement in wireless sensor networks'', Wireless Netw. 14, No. 3, 347--355 (2008; \url{doi:10.1007/s11276-006-0724-8})]. Our approximation ratio for {\textsf {ST-MSP}} is \(1+\ln (\varDelta -1)+\epsilon \) in an arbitrary normed space, which in \(\mathbb {R}^2\) reduces to \(1+\ln 4+\epsilon < 2.3863 +\epsilon \). For {\textsf {SF-MSP}} we give a simple \(\varDelta \)-approximation algorithm, improving the folklore ratio \(2(\varDelta -1)\). Finally, we generalize and simplify the \(\varDelta \)-approximation of
\textit{G. Calinescu} [Discrete Optim. 14, 17--33 (2014; Zbl 1308.90186)] for the 2-Connectivity-\({\textsf {MSP}}\) problem, where \(G[R \cup S]\) should be 2-connected.
For the entire collection see [Zbl 1317.68008].On the optima localization for the three-machine routing open shop.https://zbmath.org/1460.900852021-06-15T18:09:00+00:00"Chernykh, Ilya"https://zbmath.org/authors/?q=ai:chernykh.ilya"Krivonogova, Olga"https://zbmath.org/authors/?q=ai:krivonogova.olgaSummary: A tight optima localization interval for the classical open shop scheduling problem with three machines was established by \textit{S. V. Sevastianov} and \textit{I. D. Tchernykh} [Lect. Notes Comput. Sci. 1461, 502--513 (1998; Zbl 0929.90040)]. It was proved that for any problem instance its optimal makespan does not exceed \(\frac{4}{3}\) times the standard lower bound. The process of proof involved massive computer-aided enumeration of the subsets of instances of the problem considered and took about 200 h of the running time to complete. This makes it seemingly impossible to use the same approach for more complicated problems, i.e. the four machine open shop for which the optima localization interval is still unknown. In this paper we apply that computer-aided approach to the three-machine routing open shop problem on a two-node transportation network. For this generalization of the plain open shop problem we derive some extreme instance properties and prove that the optimal makespan does not exceed \(\frac{4}{3}\) times the standard lower bound, thus generalizing the result previously known for the three-machine open shop.
For the entire collection see [Zbl 1458.90004].An improved approximation algorithm for the coupled-task scheduling problem with equal exact delays.https://zbmath.org/1460.900822021-06-15T18:09:00+00:00"Ageev, Alexander"https://zbmath.org/authors/?q=ai:ageev.aleksandr-l|ageev.alexander-a"Ivanov, Mikhail"https://zbmath.org/authors/?q=ai:ivanov.mikhail-s|ivanov.mikhail-m|ivanov.mikhail-gennadevich|ivanov.mikhail-fSummary: We study the coupled-task single machine scheduling problem with equal exact delays and makespan as the objective function. It is known that the problem cannot be approximated with a factor better than 1.25 unless \(\text{P}=\text{NP}\). In this paper, we present a 2.5-approximation algorithm for this problem, which improves the best previously known approximation bound of 3. The algorithm runs in time \(O(n\log n)\) where \(n\) is the number of jobs.
For the entire collection see [Zbl 1458.90004].Improved solution to data gathering with mobile mule.https://zbmath.org/1460.680222021-06-15T18:09:00+00:00"Zur, Yoad"https://zbmath.org/authors/?q=ai:zur.yoad"Segal, Michael"https://zbmath.org/authors/?q=ai:segal.michaelSummary: In this work we study the problem of collecting protected data in ad-hoc sensor network using a mobile entity called MULE. The objective is to increase information survivability in the network. Sensors from all over the network, route their sensing data through a data gathering tree, towards a particular node, called the sink. In case of a failed sensor, all the aggregated data from the sensor and from its children is lost. In order to retrieve the lost data, the MULE is required to travel among all the children of the failed sensor and to re-collect the data. There is a cost to travel between two points in the plane. We aim to minimize the MULE traveling cost, given that any sensor can fail. In order to reduce the traveling cost, it is necessary to find the optimal data gathering tree and the MULE location. We are considering the problem for the unit disk graphs and Euclidean distance cost function. We propose a primal-dual algorithm that produces a \((20 + \varepsilon)\)-approximate solution for the problem, where \(\varepsilon \rightarrow 0\) as the sensor network spreads over a larger area. The algorithm requires \(O (n^3 \cdot \Delta (G))\) time to construct a gathering tree and to place the MULE, where \(\Delta (G)\) is the maximum degree in the graph and \(n\) is the number of nodes.