prajwalkr / capacitated-k-center Goto Github PK

1. Choose any other center C_m, preferably, of maximum residual capacity, and find a path as described in Fig. 9 to C_m. Choose the path to C_m having center-client pairs such that we can do a series of edge swaps as described in Fig. 9.

....We move from solution to solution in the space of candidate solutions (the
search space) by applying local changes, until an optimal solution is found or a local optima is reached.

Change this:
It is a randomized algorithm,

[for god's sake, always mention this, this is not an approximation algorithm, it will not yield an optimal solution on everything no, and since it does yield with good probability, this is a randomized algorithm, so say it explicitly]

so it does not give the optimal solution on all sets of graphs but we get the solution for a large number of general graphs we tested on. (We have tried on at least more than 2000 general graphs easily, 15 runs will do the trick, we have done that for sure).

Also edges A, BandC cannotbe present.

Theorem: When there can be no more edge reassignments, then no center at
level l is within a distance ≤ 4 to any node in level l' ≥ l + 2 for all l.

Proof: This case is depicted in Case A. After there can be no more reassignments, let there exists such a center C at a level l which has an edge to some node P belonging to some level l’ ¿= l +
2. That is, let edge A exist. Let C’ be the center covering the node P......continue.

Theorem: When there can be no more reassignments, if a center C_l at level l is within distance <= 4 to any of the upper levels, then any center C'_< l at levels < l, will not be within a distance <=4 from any node in the domain of C_l.

Proof:
This situation is represented by Case B in the figure. We will prove by contradiction. Let us say such a case exists, that is, edge B in the figure exists. Then, we can do a series of reassignments, to reduce the degree of a center at C_>l at some level >= l + 1. This is a contradiction, since we assumed in the beginning that we have reached a local optima and there can be no more reassignments.

Next, we implemented the integer program and a partially correct local
search algorithm.

to

Next, we implemented the integer program and a randomized local
search algorithm.

Other than
this we have included a few observations which may not be much conclusive but are
our attempts on solving the problem during the summer.

to

Other than
this we have included a few observations which may not be very conclusive but are
our genuine attempts to bring out as many ideas and approaches as possible.

As shown above, we make a level structure with the set domains with center C i
by placing the domains of size l at level l <----- here

Also here, in the theorem:
no center at level l, has an edge of length ≤ 4 to any node in level l 0 ≥ l + 2 for all l <------ here

Certifying a graph for an algorithm not only has to ensure that we can show whether
a solution is possible for G or not it also involves showing that if a solution is not pos-
sible in G then it is not even possible in G 2 , G 3 . . .

We never have to ** necessarily ** show that it wont work for any G^k. If we show it cannot work for G, then, it is a no certificate, because G is the input.

The vertices must be in a metric space, or in other words IN a complete graph that
satisfies the triangle inequality. (wth? :P)

change to:

The set of vertex points in a metric space, satisfying the triangle inequality. (That's it, nothing else, keep it simple)

The page is not in "justified allignment"

In the new version of the k-center problem, the goal is to get a set S of k vertices and
an assignment h : V \ S → S, [ wrong it is, V --> S, ]of every vertex (in V) to an open center such that....

Every vertex is a client and every client is assigned to a center.

Same thing for Section 3.1:

In the final graph G S we add two more vertices s (source) and t (sink) to the vertex set
of G. We add directed edges from s to all vertices in V \ S, from each vertex in V \ S to its
neighbours in S.....

And at the end of the section:
Now it is easy to verify that, S is a capacitated dominating set in G if and only if G S
has a maximum coverage of | V \ S | from s to t equal to the total vertices in the graph.

The first [you do not know if it is the first in the world, non constant approx algos also exist] polynomial time approximation algorithm for this problem was with an ap-
proximation factor of 10. Later a 6-approximation was found which is the best up till
date while a 5-approximation works when we can assign multiple centers at a single
vertex without including the vertex in L <---- are you sure about this? Then, alright.

The complexity is of the order of O(n^7), hindering us from analyzing for larger graphs. At present it is working very well for below 40 nodes, giving almost a 100% accuracy (mention it, it is TRUE) but aft we clocked it up to 80 nodes, we found that the accuracy drops sharply to 98-99%, i.e. one or two failures for every 110 nodes. Further, we came up with minor hacks and tweaks to get the best of randomization and non-randomization in our algorithm and could get all correct on several test sets of 110 unit square graphs each. However, this still exists as a minor tweak, and we are not able to analyze pictorially for larger graphs such as 80 nodes as we did for $&lt;= 40$ nodes. We hence, tried a different approach of representing it as a bipartite graph, but that was not possible by networkx library. We would need a better method to analyze large graphs of >= 80 nodes.

In the acknowledgement page update my university name to "SRM University"
The name is "SRM" only as recognized by UGC. What you have written is just what it stands for but not the name of the college.

In this section we perform further analysis of accuracy of the randomized algorithm by using more realistic graph structures.
Approach:
After Sir enlightened us that results on random graphs are not very conclusive, he also added a suggestion of building a graph from random points taken in a unit square. The ideas are as follows:
In a unit square, choose N random points.
Calculate the distance between all possible pairs of these N points using different L^p norms, for p >= 1.
Choose a $W$, to denote the maximum distance possible between two points connected by an edge while forming a graph.
Build the graph, with the N random points as nodes and add edges (a,b) if distance between (a,b) is <= W, for all a,b N.
Use this graph to obtain the optimal K with L = N/10.
Use the same graph to check if the randomized local search algorithm yields the optimal solution with the above K and L.

\subsection
Why the unit square approach led to more sound analysis?
Even though this did not strike at first on why this will be in any manner better than using random graphs, we decided to proceed with the implementation. During our visualization of the graphs created, we saw that this method was indeed better, in the sense that the graphs had local clusters, articulation points, isolated vertices, cliques and smoother variation in the degrees of the nodes.

@SagarSahni

When specifying randomized and non-randomized local search case, only the getVmax() function is different. So,that we don't have redundant pieces of code.

With this, I think the report is done!