  We consider the classic problem of envy-free division of a heterogeneous good
("cake") among several agents. It is known that, when the allotted pieces must
be connected, the problem cannot be solved by a finite algorithm for 3 or more
agents. The impossibility result, however, assumes that the entire cake must be
allocated. In this paper we replace the entire-allocation requirement with a
weaker \emph{partial-proportionality} requirement: the piece given to each
agent must be worth for it at least a certain positive fraction of the entire
cake value. We prove that this version of the problem is solvable in bounded
time even when the pieces must be connected. We present simple, bounded-time
envy-free cake-cutting algorithms for: (1) giving each of $n$ agents a
connected piece with a positive value; (2) giving each of 3 agents a connected
piece worth at least 1/3; (3) giving each of 4 agents a connected piece worth
at least 1/7; (4) giving each of 4 agents a disconnected piece worth at least
1/4; (5) giving each of $n$ agents a disconnected piece worth at least
$(1-\epsilon)/n$ for any positive $\epsilon$.
