Let me try a different approach.
I rethought it and maybe what I need is a minimum spanning tree with
a twist. I.e. building m spanning trees in stages and in parrallel.
Lets say I want to build m spanning trees and I have
an input graph of n verticies and z edges in the graph.
lets assume there are no disconnected components.
At each stage we add an edge(or none) to each of the graphs.
If we add an edge to the same city on some subset u of the graphs and
the edge cost
is C_k then the cost for each edge is C_k/|u| and totally C_k.
(the edge cost depends on the city so all incomming edges to a city
have the same cost)
Again note that I must build all the spanning trees
in parrallel and in stages because time matters here.
Simple calculation shows, that the complexity as it is now, is
O(((z+1)^n)^m) which is huge.
The input graph is directed but bidirectional, i.e. if there is an edge
in one direction,
there is an edge in the other direction with different costs to traverse
If I'll translate it to a problem domain it could be seen as salesman
trying to branch out to another city a branch at a time.
The cost of branching is the cost of an edge.
If we have m salesmen offices and they are branching to the same city
at the same time they can share the cost of buying the building.
(the building has space for all salesmen if need be)
> -----Original Message-----
> From: leiboviche [mailto:leiboviche@...]
> Sent: Monday, March 14, 2005 5:07 PM
> To: firstname.lastname@example.org
> Subject: [hackers-il] Re: what problem is it?
> I just wanted to note, that if we're speaking of Euclidian or
> Euclidian space graph there are some very good approximation
> schemes for it (the I think it stands currently of 1.5
> approximation) if you want references - do tell. BTW Nadav
> Hare'l has summurized my thoughts of the matter, it was like
> a magical story I thought of the "salesmen of the world
> unite" sollution and suddenly Nadav wrote it.
> --- In email@example.com, Tzahi Fadida <tzahi_ml@f...> wrote:
> > Hi,
> > I am trying to charecterise a problem I have for my thesis.
> > I am not a graphs person so I need some help with this one.
> > I know its probably at least a TSP problem.
> > I.e. shortest path a person can take to visit
> > all his target cities. shortest could translate to
> > cab costs or cost to sequentially scan a file(which is what
> I am working
> > on).
> > Now comes the catch, what if you have S salesmans
> > traveling to all the same cities and if they travel to the
> > same destination together at the same time they can share a
> cab and thus
> > each of them pays 1/S, i.e. the cab still only gets the fair fee
> > as if only one person traveled. btw, at the start they don't
> > necessarily start at the same city.
> > My question is, what is the (closest) problem in the literature? I
> > heard something about Multiple traveling salesman problem but I am
> > searching for a specific one where it has my kind of cab sharing
> > costs. maybe some way to reduce it to regular TSP... I
> heard something
> > about MTSP with time windows but I am not sure it fits.
> > Aside from the problem, if there is some approximation/heuristic or
> > anything please tell.
> > Regards,
> > tzahi.
> > * - * - *
> > Itzhak Fadida
> > MSc Student
> > Information System Engineering Area
> > Faculty of Industrial Engineering & Management
> > Technion - Israel Institute of Technology
> > Technion City, Haifa, Israel 32000
> > Technion Email: Tzahi@T...
> > Alternative Email: TzahiFadida@M...
> > Office Phone(from Israel): 04-8292226
> > Office Location: Technion, Cooper Bldg. room 427.
> > * - * - * - * - * - * - * - * - * - * - * - * - * - * - *
> > WARNING TO SPAMMERS: see at
> > http://members.lycos.co.uk/my2nis/spamwarning.html
> Yahoo! Groups Links