Sign up ×

For traveling salesman problems involving physical distances, one often has the “triangle inequality”: If $i, j,$ and $k$ represent three cities, then the distance $d_{ij}$ from $i$ to $j$ naturally satisfies

$$ d_{ij} ≤ d_{ik} + d_{kj}.$$

The analogous inequality might not hold for $t_{ij}$ in job-scheduling problems. I am supposed to try to come up with a realistic scenario in which it would not hold but I can't quite think of one.

What is a realistic example of a job-scheduling problem in which the triangle inequality does not hold for the costs?

share|cite|improve this question
What's your question? – MJD Jan 18 '13 at 3:20
I am trying to think of a realistic scenario i.e a job scheduling problem where this inequality doesn't necessarily hold – zxcvbnm Jan 18 '13 at 3:35
@zxcvbnm What does $t_{ij}$ represent in a job scheduling problem? How does it depend on $i$ and $j$? What do $i$ and $j$ represent, jobs or machines? In other words, what's your question? – Erick Wong Jan 18 '13 at 5:18
t as in time from i to j as in start to finish – zxcvbnm Jan 18 '13 at 5:38
Would you be able to provide a reference to where this is defined? Ideally one where there is an example of an instance of a "job-scheduling problem". – Douglas S. Stones Jan 18 '13 at 9:39

1 Answer 1

If $i$,$j$, and $k$ represent three cities, then consider $t_{ij}$ which is the time is takes to work out what the fastest route from city $i$ to city $j$ is. (For example, by doing an $A^*$ search, the more roads we have to consider the longer it takes).

If there are direct high-speed roads joining $k$ to both $i$ and $j$ then $t_{ik}$ and $t_{kj}$ will be very small. (It will take very little time to prove that these roads provide the fastest route).

However, the fastest route from $i$ to $j$ may not go via $k$, so this information is not at all useful, and the time $t_{ij}$ to compute the fastest route could easily be greater then $t_{ik} + t_{kj}$.

share|cite|improve this answer

Your Answer


