Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [iterated-rounding]

Iterated rounding technique has been recently used in approximation algorithms and can be used to design even the exact algorithms. This technique exploits the structural nature of the optimal extreme solutions of the linear programming formulation.

-1
votes
0answers
56 views

Approximate Multi Covering with Randomized Rounding

In the set multicover problem we are given a set $N$ of $n$ elements and a set $S$ of $m$ subsets of $N$. Additionally, each element has a coverage requirement (the number of times it has to be ...
0
votes
0answers
60 views

Iterative algorithms and Lyapunov functions

Consider an iterative algorithm of the form $x^{t+1} = x^t - \eta g(x^t)$. (..if necessary feel free to assume that a function $L$ is explicitly known such that $g = \frac{\partial L}{\partial x}$..). ...
4
votes
0answers
135 views

Concentration Bounds for Dependent Rounding

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
6
votes
1answer
588 views

Is there a example of Iterative Rounding in Approximation Algorithms for vertex weighted Graphs?

I am referring to the "Iterative Rounding" technique used by Kamal Jain for Steiner Network problem to obtain $2$ approximation factor algorithm. Is there any example where this technique is used for ...
5
votes
0answers
74 views

A question regarding Improved Algorithm for Degree Bounded Survivable Network Design Problem

In the paper "Improved Algorithm for Degree Bounded Survivable Network Design Problem", by N. Vishnoi and A Louis, have used the iterated rounding approach in a similar as by Jain in designing the ...