Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
45 views

Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

Suppose I have a linear program $LP1=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}\}$ for some polytope $\mathcal{P}\subseteq [0,1]^n$, which is known to have fractional extreme points. Suppose ...
gov's user avatar
  • 341
0 votes
0 answers
68 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}$..). ...
gradstudent's user avatar
  • 1,453
4 votes
0 answers
162 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 ...
afshi7n's user avatar
  • 271
6 votes
1 answer
674 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 ...
singhsumit's user avatar
5 votes
0 answers
81 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 ...
singhsumit's user avatar