Intereting Posts

Find an abelian infinite group such that every proper subgroup is finite
How to find the smallest $n$ such that $n^a\equiv 1 \pmod p$
Does multiplying polynomials ever decrease the number of terms?
Can all real/complex vector spaces be equipped with a Hilbert space structure?
How to apply Gaussian kernel to smooth density of points on 2D (algorithmically)
Advantage of ZF over other set theories such as New Foundation
If xy + yz + zx = 1, …
Is Gaussian integral the only one that can be easily solved by this double integral trick?
Sparsest matrix with specified row and column sums
Infinite product probability spaces
Prove that if $i$ and $j$ are integers, the $\langle a^i \rangle = \langle a^j \rangle$ iff $i=\pm j$
Converse of interchanging order for derivatives
Metric and Topological structures induced by a norm
Sheafification of a presheaf through the etale space
Cantor's Teepee is Totally Disconnected

Some people agree to carpool, but they want to make sure that any

carpool arrangement is fair and doesn’t overload any single person

with too much driving. Some scheme is required because none of them

goes to work every day, and so the subset of them in the car varies

from day to day.Let the people be labeled in a set $S = \{p_1,…,p_k\}$. We say that

thetotal driving obligationof $p_j$ over a set of days is the

expected number of times that $p_j$ would have driven, had a driver

been chosen uniformly at random from among the people going to work

each day. That is, suppose the carpool plan lasts for $d$ days, and on

the $i^{th}$ day a subset $S_i \subseteq S$ of the people go to work.

Then the total driving obligation $\delta_j$ for $p_j$ can be written

as $\delta_j = \sum_{i:p_j\in S_i} \frac{1}{|S_i|}$. Ideally, we’d

like to require that $p_j$ drives at most $\delta_j$ times, but

$\delta_j$ may not be an integer.A

driving scheduleis a choice of a driver for each day$-$a sequence

$p_{i_1}, p_{i_2},…,p_{i_d}$ with $p_{i_t}\in S_t-$and that afairis one in which $p_j$ is chosen as a driver on at

driving schedule

most $\lceil \delta_j \rceil$ days.

- Writing a GCD of two numbers as a linear combination
- Knuth's algorithm for Mastermind question
- Heuristics for topological sort
- Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$
- Efficient way to determine if a number is Perfect Square
- Bounds on the gaps in a variant of polylog-smooth numbers.

Prove that for any sequence of sets $S_1,…,S_d$, there exists a fair driving schedule.

Give an algorithm to compute a fair driving schedule that is polynomial in $k$ and $d$.

I have a few questions here. My first question has to do with $\delta_j$. Namely, what does the sum truly represent? I don’t really understand the notation $i:p_j\in S_i$. Are we summing over all $i$ values, all values in $S_i$, or what?

I’m also confused about number 1. A sequence of sets $S_1,…,S_d$ represents a set of people $S_1$ to $S_d$ through $d$ days. We want to show that there is a fair driving schedule for this set, so we need to show that $p_i$ drives on at most $\lceil \delta_i \rceil$ days for all people $p_i$. However, we’re not even told how many people there are in each set, so how can we determine what $\delta_i$ should be?

Again, this confusion may stem from my misunderstanding of the notation in the summation, so if someone could clear that up I would greatly appreciate it.

I’m not really sure how we can efficiently construct an algorithm that computes a fair driving schedule. Among which ideas should I look for insight here? I was thinking this was somewhat reminiscent of network flow problems, but I’m not entirely sure.

- “Planar” graphs on Möbius strips
- Hamiltonian Path Detection
- Ramsey Number proof: $R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$
- how can be prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$
- A graph problem
- Finding location of a point on 2D plane, given the distances to three other know points
- Coloring a Complete Graph in Three Colors, Proving that there is a Complete Subgraph
- How to calculate discrepancy of a sequence
- associativity in graph theory
- Is this true: any bipartite graph with unbalanced vertex parity is not Hamiltonian?

There should be always a fair driving schedule since you can model this problem as a flow network. The source is connected with all persons and the capacity of an edge from the source to a person $p_j$ is $\lceil\delta_j\rceil$. The next step is to connect every person with each of his working days. The capacity of each of this edges is $1$. The last step is to connect each day with the sink with capacity $1$.

Applying the max-flow min-cut theorem to our flow network, we can see that the maximal flow of our network is equal to the number of days, since the minimal cut splits our network into the sink and all other nodes.

Explanation: Without loss of generality, we can assume that each person works at least one day and there are no days without workers. Therefore we exclude all cuts running through an edge which connects a person with a day. The cut which splits our network in source and all other nodes is not minimal since

$$\sum_j\lceil\delta_j\rceil\ge\sum_j\delta_j= \text{number of days}.$$ The mixed cases are excluded with the combination of the abovementioned arguments.

In conclusion, the maximal flow in out network can be retranslated to our original problem in the following way: If the flow from the node corresponding to person $p$ to the node corresponding to day $t$ is $1$, than $p$ is the driver on $t$.

Note that there are algorithms to determine the maximal flow like the Ford-Fulkerson-Algorithm.

It seems to me that you could describe this situation as a bipartite graph with the one partition representing the people and the other partition representing the days with an edge between them if that person rides on that day. You could apply a greedy style algorithm matching edges to a day vertex such that each day vertex is adjacent to at most one matched edge (ignoring that person vertices may be adjacent to multiple). You could for each day pick the person whose current ‘filled’ obligation is least.

Using the graph that I described, as I understand, if $N(p_i) = \{S_{j_n}\}_n$, then $\delta_i = \sum_{k=1}^{n} \frac{1}{N(S_{j_n})}$, that is to say, each time that a person rides in the carpool they share the responsibility of driving with each other person in the car. We want to avoid any one person having to drive more than their fair share of the time.

In my example, $N(p_1) = \{S_1, S_3, S_4, S_6\}$ and $\delta_1 = \frac{1}{3} + \frac{1}{2} + \frac{1}{3} + \frac{1}{3} = 1.5$ so at the sixth day, $p_1$ would feel it fair for him/her to have driven two days. Notice also for day 5, there is only one driver available, so $p_4$ automatically feels it is fair that they had to drive then.

The first algorithm that comes to my mind (which is likely not the best) is to look at day one’s riders and pick the first person that comes to mind whose filled obligation is least. Do the same for day 2 and so on. If at any point you will have accidentally put someone over what they feel is fair, then on a previous day that they are currently designated to drive, have someone else whose current filled obligation is least drive instead.

Notice that in my algorithm, it would initially assign $p_1$ to drive on day one and then $p_2$ to drive on day two, but when we reach day 3 it would attempt to assign driving duty to $p_1$ again, putting him at driving two days while $p_1$ would feel it unfair as he expects to have only had to drive $\frac{1}{3}+\frac{1}{2}$ days, so we backtrack to day 1 and pick someone different to drive then instead, namely $p_3$.

Someone better than me could come along and give us an idea of how good or bad this algorithm is, or provide a counter example for when it would fail. My intuition tells me that it should work, though I’m only starting to learn this subject myself. My main point for posting was to hopefully help give an idea how to interpret the variables.

- Interesting closed form for $\int_0^{\frac{\pi}{2}}\frac{1}{\left(\frac{1}{3}+\sin^2{\theta}\right)^{\frac{1}{3}}}\;d\theta$
- Measure Theory – Problem with definition about simple functions
- Viewing forcing as a result about countable transitive models
- How to prove that for all natural numbers, $4^n > n^3$?
- Parametric Equations Problem
- Is the hyperbola isomorphic to the circle?
- Extending a Homeomorphism between open ball and open box of $R^n$
- Bipartite graph non-isomorphic to a subgraph of any k-cube
- How to calculate integral of $\int_0^\sqrt4\!\sqrt\frac{x}{4-x^{3/2}}\,\mathrm{d}x$
- Does 'let x be a member of S…' require axiom of choice?
- How to define $x^a$ for arbitrary real numbers $x$ and $a$
- Conformal map from a lune to the unit disc in $\mathbb{C}$
- map from $\mathbb{C}$ to $\mathbb{C}/L$ is open map?
- Question on Good Pairs
- How can I pick up analysis quickly?