How to restart service after the app is killed from recent tasks

Override onTaskRemoved() in your service and use alarm manager to start the service again. Below is code from our app that does the same and works fine:

@Override
public void onTaskRemoved(Intent rootIntent) {
    super.onTaskRemoved(rootIntent);

    Log.d(TAG, "TASK REMOVED");

    PendingIntent service = PendingIntent.getService(
            getApplicationContext(),
            1001,
            new Intent(getApplicationContext(), MyService.class),
            PendingIntent.FLAG_ONE_SHOT);

    AlarmManager alarmManager = (AlarmManager) getSystemService(Context.ALARM_SERVICE);
    alarmManager.set(AlarmManager.ELAPSED_REALTIME_WAKEUP, 1000, service);
}  

As you may want to send location periodically even in the case if the service gets killed on low memory (or for any reason), I suggest you to handle the uncaughtException to restart it after N seconds. This is how we have done in our app that works perfectly:

private Thread.UncaughtExceptionHandler defaultUEH;
private Thread.UncaughtExceptionHandler uncaughtExceptionHandler = new Thread.UncaughtExceptionHandler() {

    @Override
    public void uncaughtException(Thread thread, Throwable ex) {
        Log.d(TAG, "Uncaught exception start!");
        ex.printStackTrace();

        //Same as done in onTaskRemoved()
        PendingIntent service = PendingIntent.getService(
                getApplicationContext(),
                1001,
                new Intent(getApplicationContext(), MyService.class),
                PendingIntent.FLAG_ONE_SHOT);

        AlarmManager alarmManager = (AlarmManager) getSystemService(Context.ALARM_SERVICE);
        alarmManager.set(AlarmManager.ELAPSED_REALTIME_WAKEUP, 1000, service);
        System.exit(2);
        }
    };

Note: I THINK and I remember I verified it on Kitkat that START_STICKY does not work on Kitkat and higher API levels. Please verify this for yourself.

MORE:
As you do loc sending periodically, you may have to consider the deep sleep mode. To get things work in deep sleep, use WakefulBroadcastReceiver combined with AlarmManager. Take a look at my other post How to use http in deep sleep mode.

UPDATE:
This solution does not work (in fact need not to work) if user "FORCE STOP" the application from Settings. This is good in fact as restarting the service is not a good way if user himself wants to stop application. So, it is fine.