Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user$alpha$-approximate Reductions: a Novel Source of Heuristics for Better Approximation Algorithms
57
0
0.0
(
0
)
Added by
Prafullkumar Tale Mr
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a $tilde O(sqrt n)$-approximation, while the best current negative result is APX-hardness. All current approximation algorithms for the problem build on the same paradigm: compute a set $E$ of edges (called a emph{planarizing set}) such that $Gsetminus E$ is planar; compute a planar drawing of $Gsetminus E$; then add the drawings of the edges of $E$ to the resulting drawing. Unfortunately, there are examples of graphs, in which any implementation of this method must incur $Omega (text{OPT}^2)$ crossings, where $text{OPT}$ is the value of the optimal solution. This barrier seems to doom the only known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than $O(sqrt n)$-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm that, given a bounded-degree graph $G$ and a planarizing set $E$ of its edges, computes another set $E$ with $Esubseteq E$, such that $|E|$ is relatively small, and there exists a near-optimal drawing of $G$ in which only edges of $E$ participate in crossings. This allows us to reduce the Crossing Number problem to emph{Crossing Number with Rotation System} -- a variant in which the ordering of the edges incident to every vertex is fixed as part of input. We show a randomized algorithm for this new problem, that allows us to obtain an $O(n^{1/2-epsilon})$-approximation for Crossing Number on bounded-degree graphs, for some constant $epsilon>0$.
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 observed variables whose edges represent either all direct causal relationships or, less restrictively, a superset of causal relationships (identified, e.g., via conditional independence tests or a domain expert). Our goal is to recover the directions of all causal or ancestral relations in $G$, via a minimum cost set of interventions. It is known that constructing an exact minimum cost intervention set for an arbitrary graph $G$ is NP-hard. We further argue that, conditioned on the hardness of approximate graph coloring, no polynomial time algorithm can achieve an approximation factor better than $Theta(log n)$, where $n$ is the number of observed variables in $G$. To overcome this limitation, we introduce a bi-criteria approximation goal that lets us recover the directions of all but $epsilon n^2$ edges in $G$, for some specified error parameter $epsilon > 0$. Under this relaxed goal, we give polynomial time algorithms that achieve intervention cost within a small constant factor of the optimal. Our algorithms combine work on efficient intervention design and the design of low-cost separating set systems, with ideas from the literature on graph property testing.
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 to any non-trivial factor, and little progress has been made despite its importance in modeling activity allocation under uncertainty. We consider a special case that we call Feedback MAB, where the reward obtained by playing each of n independent arms varies according to an underlying on/off Markov process whose exact state is only revealed when the arm is played. The goal is to design a policy for playing the arms in order to maximize the infinite horizon time average expected reward. This problem is also an instance of a Partially Observable Markov Decision Process (POMDP), and is widely studied in wireless scheduling and unmanned aerial vehicle (UAV) routing. Unlike the stochastic MAB problem, the Feedback MAB problem does not admit to greedy index-based optimal policies. We develop a novel and general duality-based algorithmic technique that yields a surprisingly simple and intuitive 2+epsilon-approximate greedy policy to this problem. We then define a general sub-class of restless bandit problems that we term Monotone bandits, for which our policy is a 2-approximation. Our technique is robust enough to handle generalizations of these problems to incorporate various side-constraints such as blocking plays and switching costs. This technique is also of independent interest for other restless bandit problems. By presenting the first (and efficient) O(1) approximations for non-trivial instances of restless bandits as well as of POMDPs, our work initiates the study of approximation algorithms in both these contexts.
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 which given demands for the items must be satisfied. Ordering a set of items incurs a cost according to a set function, with properties depending on the problem under consideration. Demand for an item at time $t$ can be satisfied by an order on any day prior to $t$, but a holding cost is charged for storing the items during the intermediate period; the goal is to minimize the sum of the ordering and holding cost. Our approximation factor for both problems is $O(log log min(N,T))$; this improves exponentially on the previous best results.
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 there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance $r$ if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors. We present a 3.11-approximation algorithm for the one-tier version and a PTAS for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P $ e$ NP.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
