Why can't we define absolute rest? If, according to the theory of relativity, as objects gain velocity and approach the speed of light then time for them slows down, why can't we define absolute rest as the inertial frame in which time is running the fastest?
 A: 
why can't we define absolute rest as the inertial frame at which time is running the fastest?

We cannot define absolute rest in that manner because it is not unique. In Abe’s reference frame Abe’s time runs the fastest and Bob, Cam, and Don’s times all run slower. But in Bob’s frame Bob’s time runs he fastest and Abe, Cam, and Don’s times all run slower. Similarly for Cam and Don. 
The thing is that these are not mere differences in opinion. Each can use the same experimental techniques to prove unambiguously that their clocks run the fastest in their frame and that everyone else’s clocks are slow in their frame. So every frame has equal right to be called the absolute rest frame by that criterion. 
A: Your reasoning is an example of begging the question. That is, by stating that

objects gain velocity and approach the speed of light then time for
  them slows down

you're assuming that an absolute rest frame exists (for the object to gain velocity relative to) as a premise in order to conclude that an absolute rest frame exists 
As a comment points out, an object with speed near $c$ in some inertial frame of reference is stationary in its own inertial frame of reference. Thus, according to the clocks at rest in either frame, it is the other, relatively moving clocks that run slow.
Yes, this symmetric time dilation is counter-intuitive which is why your question (and variations on the theme) are frequently asked questions here.
That's why John Rennie created this question and answered it:  How can time dilation be symmetric?
A: It is in no way possible to tell, whether inertial laboratory is truly “moving” or is “at rest”, or to detect “ether drift”, or “absolute frame”.
Lorentz's Ether theory was created between 1892 and 1895 and was based on a completely motionless aether. It explained the failure of the negative aether drift experiments to first order in v/c by introducing an auxiliary variable called "local time" for connecting systems at rest and in motion in the aether. In addition, the negative result of the Michelson–Morley experiment led to the introduction of the hypothesis of length contraction in 1892. However, other experiments also produced negative results and (guided by Henri Poincaré's principle of relativity) Lorentz tried in 1899 and 1904 to expand his theory to all orders in v/c by introducing the Lorentz transformation. In Lorentz theory one – way speed of light is isotropic only in the Ether, and in all moving in Ether inertial frames it is ansotropic, even though observers in these laboratories in no way are able to detect any anisotropy.
Special relativity assumes, that „preferred“ frame does not exist even in principle and one-way speed of light is equal c by definition in all inertial reference frames. In a sense every observer’s frame is “rest frame” and all other stuff moves relatively to it, not vice versa. Hence, relatively moving inertial observers will draw different conclusions about the simultaneity of spatially separated events (relativity of simultaneity).
Because the same mathematical formalism occurs in both, it is not possible to distinguish between LET and SR by experiment.
In this regard, the remark of a proponent and popularizer of the theory of relativity, M. von Laue, should also be clear, who wrote: “…it was experimentally impossible to make a choice between this theory (the Lorentz theory) and Einstein’s theory of relativity, and if the Lorentz theory nonetheless took a back seat – even though it still has proponents among physicists – this then undoubtedly occurred due to reasons of a philosophical nature”
This paper simulates all kinematic effects of SR by simplest methods of classical mechanics.
It is important to note, that it is not possible to measure the one – way speed of light even in principle. We can only measure by means of a single clock round – trip speed of light, which is always equal to c (look for Michelson – Morley experiment)
Inertial observers (say Ben and Tom) conduct measurements by means of synchronized clocks. Before conducting any measurement, these observers must synchronize clocks in their frames. As I have already mentioned, SR employs Einstein – synchronization, which assumes isotropy of speed of light, that leads relativity of simultaneity. In that case, if Ben and Tom synchronize clocks by Einstein,  Ben will measure that Tom is „slower and shorter“ and  Tom will  see that Ben is „slower and shorter“ . 
In his first paper on the special theory of relativity, Einstein indicated that the question of whether or not two spatially separated events were simultaneous did not necessarily have a definite answer, but instead depended on the adoption of a convention for its resolution.
Conventionality of distant simultaneity allows another, broader synchronization convention (Reichenbach‘s),  that allows anisotropic one – way speed of light but keeps round-trip speed of light  isotropic.
According to foregoing, inertial observers may adjust their tools (synchronize clocks) the way they wish. They can even introduce universal time (like absolute time in Lorentz theory). In this case Ben‘s clock may be Einstein – synchronized and Tom‘s Reichenbach – synchronized.  In this case Ben will measure, that Tom is „slower and shorter“, but Tom (since he moves in Ben‘s frame)  will measure, that Ben is „faster and longer“.
Hence, even though Ben and Tom cannot know which frame is „the absolute one“, by employing different synchronization procedures they can make „the other clock“ ticking at any rate they wish; slower, faster or even at the same as his own.
The same applies to the relativistic Doppler effect
If someone insists, that “Tom is definitely slower than Ben and Ben is definitely slower than Tom”, please ask the following question:
Tom is in the center of circumference of arbitrarily large diameter and is holding a source of monochromatic light. Ben is rotating around Tom. Will Ben see Tom’s clock ticking faster or slower? Why?  Purely inertial Huck moves tangentially to the circumference. When Huck is “touching” the circumference, he momentarily coincides with Ben. At this moment Huck is moving tangentially to wave front.  Will Huck see Tom’s clock ticking slower of faster? Why?
A: In special rativity there is no absolute rest. Time runs equally fast in any inertial reference frame. However, if you insist, you could use the cosmological microwave background to fix a unique reference frame. Also no laboratory can be isolated from gravitational waves, so it will in principle always be possible to detects its speed with respect to the rest of the universe. 
Wikipedia:
CMBR dipole anisotropy
From the CMB data it is seen that the earth appears to be moving at 368±2 km/s relative to the reference frame of the CMB (also called the CMB rest frame, or the frame of reference in which there is no motion through the CMB). The Local Group (the galaxy group that includes the Milky Way galaxy) appears to be moving at 627±22 km/s in the direction of galactic longitude l = 276°±3°, b = 30°±3°.This motion results in an anisotropy of the data (CMB appearing slightly warmer in the direction of movement than in the opposite direction).
