Computing the volume of partitions in boolean cubes
รุ่นแก้ไขเมื่อ 09:34, 30 มีนาคม 2550 โดย Jung (คุย | มีส่วนร่วม) (→ไอเดียอื่นๆ #2: a bit more details)
ที่มา
จำไม่ได้ละ
ปัญหา
We have the n-dimensional unit cube:
.
The unit cube has vertices (corners). For any subset of k vertices, the partitions are defined as follows: the partition contains all points in the cube closer to v, with respect to -norm, than any other vertices in .
Question
What is the volume of 's?
ความคืบ
- Just proved that each partition defines a convex set.
- hence, we can at worst calculate the volume for each partition in using simulated annealing MCMC of Vempala and Lovasz. But this straightforward approach is inefficient if is large because the total run-time will be where can be as much as . Actually, we know that if , the volume of each partition will be simply by symmetry.
- I don't understand why the running time is ? Where does k come from? Is it from the complexity of the partition? Or... is it from the fact that you have to compute the volume of every partition? (do you?) But having k in the factor should be fine, right? Because you have to specify k points (for S) anyway. Am I missing something here? -- Jittat 23:30, 28 มีนาคม 2007 (ICT)
- hence, we can at worst calculate the volume for each partition in using simulated annealing MCMC of Vempala and Lovasz. But this straightforward approach is inefficient if is large because the total run-time will be where can be as much as . Actually, we know that if , the volume of each partition will be simply by symmetry.
- To DO: The structure of this problem might allow a better, simpler algorithm. There are a lot of orthogonal hyperplanes.
ไอเดียอื่นๆ #1
reduce the problem to other cube in smaller dimensions. hypercube embedding? -- to be continued ...
ไอเดียอื่นๆ #2
- Starting from the case (every point is a reference point). This case divides the volume up equally to for each partition. The idea is, for each , assign the volume that v would have had (that is, 2^n) if it were to be in to its closest vertices in (we deal with ties by dividing the volume equally). The problem is how well this method approximate the volume? , or in more extreme, is this method exact??
- Very interesting. Intuitively, it should give an exact answer. But the way you're dividing volume might not work. Here's some argument. Here I assume that |S|>1. First of all, for very point v in S, , i.e., it always takes its little cube. Now think of the way you're dividing little cubes associated with points not in S. Think of the case of 5 dimensions. Let's point u=(1,1,1,1,1), and it is not in S. The closes points to u in S are a=(0,0,1,1,1), b=(0,1,0,1,1), and c=(1,1,1,0,0). Now, note that a and b are closer to each other than to c. I guess that in this case, the volume of u should go to c more than to a or b. (I haven't proved it though.)
- Ok; there is a very simple example in the 3-dimensional unit cube which shows that the method is not exact. Let S = {(0,0,0), (1,1,1)}. Let u = (0,0,1) so that u is closer to (0,0,0) than (1,1,1). However, the partition of u is structured as alittle cube which has one corner at (1/2, 1/2, 1). This point, including some points nearby (which totally have non-zero measure), is closer to (1,1,1) more than (0,0,0). Hence, some volume of u will go to (1,1,1).
- I make a simple experiment by generating points randomly within the partition of u; about 83% of the volume of u goes to (0,0,0), and the rest goes to (1,1,1). To me, it's interesting if I can explain/derive a formula for this 0.83:0.17 ratio -- Jung 15:41, 30 มีนาคม 2007 (ICT)
- Maybe a better way to distribute the volume might be to look at the subspace spanned by points in S closest to u, and compute the volumes of each partition (recursively).
- Anyway, this technique suffers from the fact that maybe the number of points not in S is exponential. --- Jittat 16:10, 29 มีนาคม 2007 (ICT)
- How about this vague idea? Consider point u in S. Find set C of closest points to u in S. (Should take time for each u.) I think that the distance from u to C should say something. Furthermore, we might be able look at how u and points in C share the volume (of something?) by considering some subspace. (There, we recurse. I guess that we won't suffer from the exponential blows up because, it seems that, we have only one subproblem.) --- Jittat 17:18, 29 มีนาคม 2007 (ICT)
- Alright. This is broken. You can't find the volume with only closest points. --Jittat 22:56, 29 มีนาคม 2007 (ICT)
- Since we are trying to make things discrete, one thing to ask is whether the volume of each discrete? and how large the range is? If yes, we may hope to compute the exact volume.
- Another thing to look at is what is the complexity of this problem?. It looks like a #P-hard problem but may not be .... This problem is very similar to the following (which is known to be #P-hard): Given a hyperplane H, count the number of points in which lies on one side of the hyperplane H. In other word, count the number of x such that . This could be thought of as counting the number of solutions for 0-1 Knapsack problem where h is weight, b is the size of knapsack, and x is the solution. Counting the solutions for NP-complete problem is #P-hard. This problem is different in that we are not given a hyperplane but instead points on hypercubes, and as far as I tried, no obvious reduction from Knapsack would work.
อ้างอิง
Hardness proof for computing volume of convex body in general