Wikipedia:Reference desk/Archives/Mathematics/2007 July 10

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 10

Roundabouts

I know you folks tend to prefer pure mathematics here, but I have a little "applied" question. I am looking for a mathematical description and/or analysis of a roundabout. For someone familiar with the parameters it should be a well defined linear algebra problem. I know that traffic patterns are often modeled mathematically, but I can’t seem to find anything specific to roundabouts. 199.172.246.196 12:14, 10 July 2007 (UTC)

I think this can be modelled as a sort of Continuous-time Markov process, but without additional details about your assumptions and goals, I can't take it much farther than that. -- Meni Rosenfeld (talk) 12:37, 10 July 2007 (UTC)

I don't know what sort of assumptions to make either. I am quite sure that it has been modeled before and I was wondering whether you knew of any existing examples. If all else fails I'll take a crack at modeling it via the Continuous-time Markov process as you have suggested. 199.172.246.196 14:09, 10 July 2007 (UTC)

Here's one (rather simplified) way to go about it. Suppose there are n exits placed equidistantly, and that each segment of the roundabout between consecutive exits can contain only one vehicle. Suppose further that crossing a segment takes time which is distributed exponentially (far from reality, but simplifies the model) with mean ${\tfrac {1}{\lambda }}$ and that it takes no time for a waiting car to enter the roundabout. We also assume that cars reach the line at the entrypoints by a Poisson process of rate $\mu$. Our state space will be $\{0,\ldots ,n\}^{n}\times \mathbb {N} ^{n}$, where each copy of $\{0,\ldots ,n\}$ represent the segment before an exit and what car is in it (no car, or a car with destination k), and each copy of $\mathbb {N}$ represent the number of cars waiting at an entrypoint.

The different transitions are somewhat complicated to present exactly, but they all follow naturally from our assumptions: For example, if some segment is occupied, there is a transition of rate $\mu$ for the entry before it to increase its car count, but if the segment is vacant, this transition will be to occupy this segment with a car of random destination.

Does this help in any way? -- Meni Rosenfeld (talk) 17:23, 10 July 2007 (UTC)

What is the purpose you are pursuing that is aided by having a mathematical model of a roundabout? Designing better roundabouts? Showing that roundabouts are a roundabout way of getting somewhere? What aspects and details need to be modelled and which may be omitted depends on the use to which the model will be put.  --Lambiam^Talk 07:59, 11 July 2007 (UTC)

Splitting a sequence into subsequences with a minimal maximal subsequence sum

I am working on a text layout application, and find myself dealing with mathematics I had not bargained for. I have asked a very similar question above, but some experimentation has proven that my original objective was not quite what I needed. Here is a rephrasing, this time with a new objective:

Let A be a sequence. Given an integer n (n<Length(A)), divide A into n consecutive subsequences, A₁ through A_n, the union of which is A (a division, D, can be thought of as a sequence of n indices, the last of which is Length(A)). Calculate the sum of the elements of each sequence, S_i. Find the maximal such sum, Max(S₁,...,S_n), which we'll call S_max.

My question is this: how may we find which division yields the smallest S_max? (Without going over each and every possibility.) — Itai (talk) 15:57, 10 July 2007 (UTC)

Can you explain directly what text layout problem you are working on, rather than trying to "mathematize" it for us? In particular, if you're trying to break a paragraph into lines, you really need to read Donald Knuth and Michael Plass's paper "Breaking Paragraphs into Lines" (originally published in Software — Practice and Experience 11 (1981), 1119–1184; reprinted in Knuth's Digital Typography, CSLI, 1999). See our word wrap article too.

The problem you give can be solved in O(n|A|) by a straightforward dynamic programming approach (compute M_ij — the maximal sum that you can get by splitting the first j elements of the sequence into i subsequences — for all i up to n and j up to |A|). Gdr 17:06, 10 July 2007 (UTC)

I've read a synopsis of the paper you mentioned, and it seems very interesting. I'll read it sometime should I obtain a copy. My own problem is that of dividing p indivisible paragraphs (well, truth be told, each consists of one question and four possible answers, but that hardly matters) between c columns. I admit I was uncertain as to what is the proper division criterion. At first I thought the best thing is to minimize the standard deviation, to make the page look prettier. Then I settled for a lesser, and seemingly much easier to accomplish, objective of minimizing the difference between the longest and shortest columns. At last I came to the conclusion that what I'm really after is "conserving paper" - making the longest column as short as possible, making for the least space-consuming page. — Itai (talk) 22:30, 14 July 2007 (UTC)

(after edit conflict) I'll avoid the term subsequence, which often does not imply contiguity (like the sequence of primes 2, 3, 5, ... is a subsequence of 1, 2, 3, 4, 5, ...). I'll use segment instead for a contiguous subsequence. Also, let a k-split of a sequence be a split into k consecutive segments, so you want an n-split.

Let m = Length(A), and let A|i denote the prefix (initial segment) of A of length i, so A|0 = (), the empty sequence, and A|m = A. Define mM(i, k) to be the minimum, over all k-splits of A|i, of the maximum of the segment sums. You can compute, incrementally, an optimal k-split of A|i, 0 ≤ k ≤ n, with the length i of the prefix going from 0 up to and including n. (This is essentially the usual algorithm for a version of dynamic programming, using a vector instead of a single value.) You only need to include 0 in the range for k when i = 0, and n only when i reaches m.

To start, mM(0, k) = 0 for all k. Assume we already have computed mM(i–1, k) for i > 0 and k in the appropriate range. We can then determine mM(i, k+1) for each relevant value of k (i.e., with k+1 in range) as follows. Each ( k+1)-split of A|i consists of a k-split of a shorter prefix A|j followed by a final segment of A|i of length i–j, so it is an extension by one segment of an initial k-split. For 0 ≤ j < i, let T_j be the sum of the final segment of A|i of length i–j. Among all ( k+1)-splits of A|i with that final segment, the best score is then max(mM(j, k), T_j). So then mM(i, k+1) is the minimum of these scores for 0 ≤ j < i.

The above only gives you the value mM(m, n) of the optimal m-split of A, not the split itself. But as you store mM in an array, you can store with each new entry mM(i, k+1) a backpointer, being the value of j that minimized the value of max(mM(j, k), T_j). Then you can trace a path back from the entry mM(m, n) to mM(j, n–1) (using the "j" stored at mM(m, n)) to ... to finally mM(0, 0).

The same procedure can be followed for many different optimality criteria, including your earlier minimization of the spread. The only requirement is that the principal of optimality is met: the score of a (k+1)-split can be expressed as a function of the score of its initial k-split and the final segment, where that function is monotonically increasing in its first argument. Then an optimal (k+1)-split can be obtained by extending a shorter optimal k-split.

Specifically for your min-max criterion, if you let j run backwards, once T_j reaches the best score you already have for mM(i, k+1), you can break from the j-loop, since it's not going to get any better.  --Lambiam^Talk 17:26, 10 July 2007 (UTC)

Thanks a million. This seems like a very good algorithm, and, amazingly, one I can understand - at least as far as this recent criterion is concerned. If by "minimization of the spread", above, you mean minimizing what I've referred to before as "standard deviation", I do not see how this can be achieved using a variation on the algorithm specified above. I suppose this will give me something to think about. I should really read more about dynamic programming. I doubt whether my own code will be worthwhile posting, but should I come up with something even barely legible, I'll put it up in a subpage of my user page, and place a reference here. Anyway, I am, of course, much obliged. — Itai (talk) 22:30, 14 July 2007 (UTC)