User andy - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:59:17Z http://mathoverflow.net/feeds/user/14630 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63882/set-covergreedy-vs-lp Set Cover:Greedy vs LP andy 2011-05-04T05:48:22Z 2012-11-05T08:26:56Z <p>Hi</p> <p>Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches?</p> <p>thanks</p> http://mathoverflow.net/questions/87250/reusing-parts-of-a-proof Reusing Parts of a Proof andy 2012-02-01T16:28:06Z 2012-02-01T17:01:04Z <p>Hi</p> <p>I have a proof for a Lemma which splits into an odd and even case.</p> <p>The proof for the even case was already published by someone else in a different context and the proof for for the odd case is very similar (but not trivial) to the even case proof.</p> <p>So how should I now proceed about the odd case proof? Is it ok if I make it clear that the odd case proof closely follows the idea of the even case proof, published by someone else? </p> http://mathoverflow.net/questions/83829/minimum-separating-subdivision-in-plane Minimum separating subdivision in Plane andy 2011-12-18T22:13:01Z 2011-12-19T07:44:29Z <p>Hi</p> <p>I was thinking about the following problem:</p> <p>Given a planar Graph embedded in the plane and a set of points $P$ contained in the faces (no face contains more than one point) I want to determine the maximum number of edges I can remove such that in the reduced graph no two points are contained in the same face.</p> <p>Although I didn't find any publications considering this problem, I guess this must have been studied before. </p> <p>Any pointers would be helpful to me.</p> <p>If $P$ only consists of two points $p,q$ it is easy since, we can just compute the shortest cycle containing either $p$ or $q$ but not both in its face.</p> <p>Thank you </p> <p>Andy </p> http://mathoverflow.net/questions/82928/characteristics-of-locally-triangle-free-graph Characteristics of locally triangle-free graph andy 2011-12-08T02:55:59Z 2011-12-08T18:34:04Z <p>Hi</p> <p>I am given a triangulation $T$ of a set of points $S$ in the plane and a disk $D$ which doesn't contain any triangle. If I now look at the subgraph $G(V,E)$ of $T$ whose vertices are the points of $S$ contained in $D$ and whose edges are the edges of $T$ which are fully contained in $D$ then what can I say about $G$, if $|V|$ is sufficiently large, lets say bigger than 4? </p> <p>Obviously $G$ is acyclic. Furthermore, a bit informal, each vertex $v$ needs to see some portion of the boundary of $D$ on both sides of any path through $v$.</p> <p>But are there any other characteristics which have to hold for $G$?</p> <p>Thank you </p> <p>andy</p> http://mathoverflow.net/questions/79321/computational-topology-paper Computational Topology Paper andy 2011-10-27T22:19:02Z 2011-11-24T22:10:43Z <p>Hi</p> <p>I am delving into the field of Computational Topology. I am aware of the books in this field, but</p> <p>could anybody tell me a nice relevant paper in this field which tackles a "typical" Computational Topology problem?</p> <p>Thank you</p> http://mathoverflow.net/questions/75245/enumerating-connected-circle-graphs Enumerating Connected Circle Graphs andy 2011-09-12T18:37:51Z 2011-09-12T19:03:54Z <p>Hi </p> <p>A circle graph is defined as the intersection graph of a set of chords of a circle.</p> <p>I'm interested in any information which might help to enumerate connected circle graphs.</p> <p>Thanks</p> <p>Andy</p> http://mathoverflow.net/questions/66990/shortest-path-in-plane Shortest Path in Plane andy 2011-06-05T21:49:56Z 2011-06-06T12:59:51Z <p>Hi</p> <p>I thought about the following problem:</p> <p>Given a polygonal subdivision of the euclidian plane where each of the polygons has a speed associated with it, and given two points s,t, I'm interested in the fastest path from s to t.</p> <p>I don't know if the problem is NP-hard or not. If the regions are convex, I have an easy 2-approximation algorithm. (Maybe there is an PTAS algorithm for the convex/general case?)</p> <p>I'm pretty sure that this problem has been studied before.</p> <p>Does anybody know any publications about it and/or has an idea how to show NP-hardness. (But after all, maybe the problem is easy.)</p> <p>Thank you</p> <p>Andy</p> http://mathoverflow.net/questions/64921/torus-in-mathcalr3 Torus in $\mathcal{R}^3$ andy 2011-05-13T19:04:56Z 2011-05-18T22:44:04Z <p>Hi</p> <p>I'm interested in packing the 3 space as dense as possible using equally sized tori whose major radius is much bigger than their minor radius in.</p> <p>Do you have any idea how to attack this problem? I'm fairly new to this topic and I haven't found many papers for non-convex objects. (I think that the torus is somehow the easiest non convex object.)</p> <p>I thought about writing some computer simulation to get a feeling for the problem. Also I think that the densest packing will be an irregular packing.</p> <p>Any comments are appreciated.</p> <p>Thank you</p> <p>Andy</p> http://mathoverflow.net/questions/63222/pr-lambda-2-x-in-g-np-model PR[$\lambda_2 > x$] in $G_{np}$ model andy 2011-04-27T20:07:26Z 2011-04-27T22:50:28Z <p>Hi</p> <p>Does anyone know of any statement relating the probability that the second largest eigenvalue of a random graph is bigger than x to the parameter p in the G_np model?</p> <p>Thanks</p> http://mathoverflow.net/questions/62890/algorithm-for-testing-satisfiable-fraction-of-linear-equations-mod-2 Algorithm for testing satisfiable fraction of linear equations mod 2 andy 2011-04-25T04:48:48Z 2011-04-25T04:48:48Z <p>Hello </p> <p>Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are ${x_1, ..., x_n}$ and for each of the $\binom{n}{2}$ $i,j$ pairs, the equation $x_i + x_j = b_{ij}$ gets generated with probability p, where $b_{ij}$ is chosen uniformly at random in $F_2$ too.</p> <p>let $\phi$ be such a system of equations und let $OPT(\phi)$ denote the maximal fraction of satisfiable equations.</p> <p>Given a constant $0 &lt; \epsilon &lt; 10^{-4}$</p> <p>I would like to come up with a deterministic polytime algorithm A, and a constant $c > 0$ such that A: </p> <p>accepts, if $OPT(\phi ) >= 1-\epsilon$ <br> rejects with high probability, if $\phi \in F_{n, c/n }$ </p> <p>My problem is that the algorithm is not allowed to (wrongly) reject any $1-\epsilon$ satisfiable $\phi$.</p> <p>My observation is that some subformula is unsatisfiable if, the subformula forms a cycle (when formulated as a graph) and a odd number of $b_{ij}$ equals 0.</p> <p>But i have no idea how to chose the c.</p> http://mathoverflow.net/questions/62779/existence-of-l1-embedding-using-lp-feasibility existence of l1 embedding using LP feasibility andy 2011-04-23T21:55:37Z 2011-04-24T03:13:25Z <p>hello</p> <p>Let (A, d) be an n-point metric space</p> <p>for $t \geq 1$,the task it to find an integer $m$ and an embedding $f : A \rightarrow R^m$ s.t. $\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq t*d(x,y)$ where $d_1$ denotes the $l_1$ norm.</p> <p>Is it possible to check if f exists, given t using linear programing?</p> <p>andy</p> http://mathoverflow.net/questions/87250/reusing-parts-of-a-proof Comment by andy andy 2012-02-01T16:45:20Z 2012-02-01T16:45:20Z @Mark Sapir I think you misunderstood me, mentioning that my proof follows the idea of the other proof is the least I would do. But I would still reuse many ideas of the original proof and I don't feel too comfortable about it. http://mathoverflow.net/questions/83829/minimum-separating-subdivision-in-plane/83845#83845 Comment by andy andy 2011-12-19T06:21:41Z 2011-12-19T06:21:41Z @Joseph O'Rourke Yes this is exactly the example I was thinking about, thank you very much for the picture. Do you know anything about this problem? @Michael Biro Yes one more vertex on the path would make the counterexample even more clear. http://mathoverflow.net/questions/83829/minimum-separating-subdivision-in-plane/83837#83837 Comment by andy andy 2011-12-19T00:50:31Z 2011-12-19T00:50:31Z and would end up with a solution of size 8. http://mathoverflow.net/questions/83829/minimum-separating-subdivision-in-plane/83837#83837 Comment by andy andy 2011-12-19T00:43:13Z 2011-12-19T00:43:13Z @Igor Rivin :Thank you for your answer. Your write: &quot;Secondly, all edges connecting two blue vertices in H′ can be collapsed. So do it, and obtain a new graph H′′.&quot; Is this true? Because if i have a rectangle which is horizontaly divided into 3 parts l,m,r. The left division is made by a single vertical edge e, and the right one is done by a vertical path of come length c, and i have a point s in r and a point t outside of the rectangle, then the smallest separating arrangement would contain only 6 edges, but if i collapse any edge connecting two blue vertices i would thusby delete the edge e http://mathoverflow.net/questions/79321/computational-topology-paper Comment by andy andy 2011-11-28T23:50:57Z 2011-11-28T23:50:57Z @Ryan Budney Yes I realized this later too http://mathoverflow.net/questions/79321/computational-topology-paper/79333#79333 Comment by andy andy 2011-10-28T15:36:33Z 2011-10-28T15:36:33Z Thanks you for the nice paper suggestion, that was what I was looking for. http://mathoverflow.net/questions/79321/computational-topology-paper Comment by andy andy 2011-10-27T23:50:40Z 2011-10-27T23:50:40Z Oh thanks I wasn't aware of this. Yes I meant more the Edelsbrunner type. http://mathoverflow.net/questions/79321/computational-topology-paper Comment by andy andy 2011-10-27T23:15:51Z 2011-10-27T23:15:51Z One which everyone uses as an example http://mathoverflow.net/questions/66990/shortest-path-in-plane/66992#66992 Comment by andy andy 2011-06-06T17:40:14Z 2011-06-06T17:40:14Z Hi Yuri Could you illustrate a situation where the problem is not well defined? http://mathoverflow.net/questions/62890/algorithm-for-testing-satisfiable-fraction-of-linear-equations-mod-2 Comment by andy andy 2011-04-26T06:29:59Z 2011-04-26T06:29:59Z i think the key observation is that the equations are randomly generated =&gt; the underlying (implication) graph is random and random graphs are have expander property. And the label covering problem (which the linear equation correspond to, i.e. unique game) is not hard on expanders. but still i have no idea how not to wrongly reject any 1-eps sat formula.