ﻻ يوجد ملخص باللغة العربية
Lokshtanov et al.~[STOC 2017] introduced emph{lossy kernelization} as a mathematical framework for quantifying the effectiveness of preprocessing algorithms in preserving approximation ratios. emph{$alpha$-approximate reduction rules} are a central notion of this framework. We propose that carefully crafted $alpha$-approximate reduction rules can yield improved approximation ratios in practice, while being easy to implement as well. This is distinctly different from the (theoretical) purpose for which Lokshtanov et al. designed $alpha$-approximate Reduction Rules. As evidence in support of this proposal we present a new 2-approximate reduction rule for the textsc{Dominating Set} problem. This rule, when combined with an approximation algorithm for textsc{Dominating Set}, yields significantly better approximation ratios on a variety of benchmark instances as compared to the latter algorithm alone. The central thesis of this work is that $alpha$-approximate reduction rules can be used as a tool for designing approximation algorithms which perform better in practice. To the best of our knowledge, ours is the first exploration of the use of $alpha$-approximate reduction rules as a design technique for practical approximation algorithms. We believe that this technique could be useful in coming up with improved approximation algorithms for other optimization problems as well.
Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. Despite extensive work, non-triv
We study the problem of learning the causal relationships between a set of observed variables in the presence of latents, while minimizing the cost of interventions on the observed variables. We assume access to an undirected graph $G$ on the observe
The restless bandit problem is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate
We give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of $N$ items and a discrete time horizon of $T$ days in
In the relay placement problem the input is a set of sensors and a number $r ge 1$, the communication range of a relay. In the one-tier version of the problem the objective is to place a minimum number of relays so that between every pair of sensors