tag:blogger.com,1999:blog-6555947.post583824111197133384..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: SoCG 2009: Epsilon-nets and covering/hitting problems.Suresh Venkatasubramaniannoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6555947.post-9683398649916297432012-03-29T17:54:27.902-06:002012-03-29T17:54:27.902-06:00Can anyone please provide links or sources from wh...Can anyone please provide links or sources from where we can learn about epsilon-nets from basic.ANIRBAN GHOSHhttp://www.blogger.com/profile/03613245518245553068noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-80678838266275449132009-06-16T07:25:22.021-06:002009-06-16T07:25:22.021-06:00The ERS is not the earliest reference. Philip Long...The ERS is not the earliest reference. Philip Long made the same observation well before they did. The ref:<br /><br /><br /><br />@inproceedings{l-upsda-01,<br /> author = {P. M. Long},<br /> title = {Using the Pseudo-Dimension to Analyze Approximation<br /> Algorithms for Integer Programming},<br /> booktitle = WADS_2001,<br /> series = "Lecture Notes Comput. Sci.",<br /> volume = "2125",<br /> year = {2001},<br /> pages = {26--37},<br />}<br /><br />Just giving credit where it is due...<br /><br />--SarielAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-64132148504096672242009-06-14T12:57:19.889-06:002009-06-14T12:57:19.889-06:00Chandra, you're right: I was oversimplifying: ...Chandra, you're right: I was oversimplifying: actually i have a post queued up on the chan-har-peled result as well, and I was going to mention your paper with Ken and Sariel as well.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-14446463966707542912009-06-14T12:50:05.370-06:002009-06-14T12:50:05.370-06:00Suresh, your general comment that the LP formulati...Suresh, your general comment that the LP formulation has to explicitly capture the geometry to be useful is not correct, in particular in the context of covering problems that you discuss in the post. The paper of Even et al. that you mentioned towards the end basically shows that the eps-net based approximations can be equivalently viewed as LP-based algorithms. Therefore the plain vanilla set cover LP that does not explicitly encode any geometry does well! What this says is that worst-case examples for the standard set cover LP cannot be encoded in certain geometric settings. The SoCG'09 paper of Ken Clarkson and Sariel Har-Peled and myself shows how the LP can be used more explicitly in the multicover setting where points may require to be covered multiple (and possible<br />different) times.<br /><br />For the weighted case, we do not know if the LP is good or bad. No lower bounds on the integrality gap worse than those for the unweighted case are known. However, the upper bound techniques via eps-nets do not generalize to the weighted case directly (see the paper of Even et al for a weak result). Sariel and I found one interesting case where LP has O(1) gap even for weighted case - covering points by axis aligned squares (or bounded aspect ratio rectangles).<br /><br />Another example of the standard LP doing well in geometric setting is for the maximum independent set problem. The paper of Timothy Chan and Sariel Har-Peled gives algorithms for independent set of pseudo-disks in the weighted case using an LP relaxation. Their LP implicitly adds clique inqualities which are quite useful.Chandrahttp://www.blogger.com/profile/00057069075567569157noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-40804970551152440962009-06-14T10:08:30.324-06:002009-06-14T10:08:30.324-06:00if you want to solve a geometric covering problem ...<i> if you want to solve a geometric covering problem and can't encode the geometry in your LP, you're stuck with the log n approximation that combinatorial set cover gives you</i><br /><br />My favorite example is Rectangle Covering Problem (covering an orthogonal polygon with a minimum number of axis-parallel rectangles). The best known approximation factor is <i>sqrt(logn)</i> using a combinatorial approach. LP-based techniques doesn't seem to provide any new insights. I am lost :(kintalihttp://kintali.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-26796806601797381592009-06-14T06:55:52.531-06:002009-06-14T06:55:52.531-06:00So what is your high level take on why generally t...So what is your high level take on why generally the epsilon net techniques don't seem to generalize to weighted problems (e.g. weighed set cover), like LP based techniques usually do? I understand why the proofs break down, but I really don't have a feel for whether this is because inherently the weighted geometric problems are harder than the unweighted geometric problems, or is it just a limitation in the proof/analysis techniques.Anonymousnoreply@blogger.com