- Personalization and adaptation of multi-media messages are well known and well studied problems. Ideally, each message should reflect its recipient's interests, device capabilities, and network conditions. Such personalization is more difficult to carry out given a compound multi-media presentation containing multiple spatially and temporally related elements. This paper describes a novel formal, yet practical approach, and an implemented system prototype for authoring and adapting compound multi-media presentations. Our approach builds on recent advances in preference specification and preferences-based constrained optimization techniques.