User andy - MathOverflow

Set Cover:Greedy vs LP

2011-05-04T05:48:22Z

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?

thanks

Reusing Parts of a Proof

2012-02-01T16:28:06Z

I have a proof for a Lemma which splits into an odd and even case.

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.

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?

Minimum separating subdivision in Plane

2011-12-18T22:13:01Z

I was thinking about the following problem:

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.

Although I didn't find any publications considering this problem, I guess this must have been studied before.

Any pointers would be helpful to me.

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.

Thank you

Andy

Characteristics of locally triangle-free graph

2011-12-08T02:55:59Z

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?

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$.

But are there any other characteristics which have to hold for $G$?

Thank you

andy

Computational Topology Paper

2011-10-27T22:19:02Z

I am delving into the field of Computational Topology. I am aware of the books in this field, but

could anybody tell me a nice relevant paper in this field which tackles a "typical" Computational Topology problem?

Thank you

Enumerating Connected Circle Graphs

2011-09-12T18:37:51Z

A circle graph is defined as the intersection graph of a set of chords of a circle.

I'm interested in any information which might help to enumerate connected circle graphs.

Thanks

Andy

Shortest Path in Plane

2011-06-05T21:49:56Z

I thought about the following problem:

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.

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?)

I'm pretty sure that this problem has been studied before.

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.)

Thank you

Andy

Torus in $\mathcal{R}^3$

2011-05-13T19:04:56Z

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.

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.)

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.

Any comments are appreciated.

Thank you

Andy

PR[$\lambda_2 > x$] in $G_{np}$ model

2011-04-27T20:07:26Z

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?

Thanks

Algorithm for testing satisfiable fraction of linear equations mod 2

2011-04-25T04:48:48Z

Hello

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.

let $\phi$ be such a system of equations und let $OPT(\phi)$ denote the maximal fraction of satisfiable equations.

Given a constant $0 < \epsilon < 10^{-4}$

I would like to come up with a deterministic polytime algorithm A, and a constant $c > 0$ such that A:

accepts, if $OPT(\phi ) >= 1-\epsilon$
rejects with high probability, if $\phi \in F_{n, c/n }$

My problem is that the algorithm is not allowed to (wrongly) reject any $1-\epsilon$ satisfiable $\phi$.

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.

But i have no idea how to chose the c.

existence of l1 embedding using LP feasibility

2011-04-23T21:55:37Z

hello

Let (A, d) be an n-point metric space

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.

Is it possible to check if f exists, given t using linear programing?

andy

Comment by andy

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.

Comment by andy

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.

Comment by andy

2011-12-19T00:50:31Z

and would end up with a solution of size 8.

Comment by andy

2011-12-19T00:43:13Z

@Igor Rivin :Thank you for your answer. Your write: "Secondly, all edges connecting two blue vertices in H′ can be collapsed. So do it, and obtain a new graph H′′." 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

Comment by andy

2011-11-28T23:50:57Z

@Ryan Budney Yes I realized this later too

Comment by andy

2011-10-28T15:36:33Z

Thanks you for the nice paper suggestion, that was what I was looking for.

Comment by andy

2011-10-27T23:50:40Z

Oh thanks I wasn't aware of this. Yes I meant more the Edelsbrunner type.

Comment by andy

2011-10-27T23:15:51Z

One which everyone uses as an example

Comment by andy

2011-06-06T17:40:14Z

Hi Yuri Could you illustrate a situation where the problem is not well defined?

Comment by andy

2011-04-26T06:29:59Z

i think the key observation is that the equations are randomly generated => 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.