Is it acceptable under US GAAP to accrue for relocation costs or must I expense them as incurred?

When you accrue an expense, it means the activity has occurred, but the cash transfer hasn't happened yet. By the same token, in your question, to accrue for relocation costs, is the same as expense it as it occurred. Dr. Expense, Cr. Payable. There is no either/or for two identical things.

I guess you meant to ask: should I accrue the expense (expense as it occurred) or should I record it when I paid for it. Yes, Under US GAAP, you need to make an accrual entry.

Can relocation expenses for a business be capitalized and then amortized over a period similar to startup costs or must they be expensed at the time incurred?