ปัญหา
หา Optimal Prefix-free Codes สำหรับ Unequal Letter Costs (ความยาวตัวอักษรไม่เท่ากัน) Encoding Alphabet มีความยาว α, β โดย α ≤ β จำกัดเฉพาะ Binary Trees
Code แทนด้วย Lopsided Tree (คล้าย Huffman Tree แทน Huffman Coding) แต่ Unequal Letter Costs ยากกว่า Huffman Problem มาก: No Polynomial-time Algorithm สำหรับ General Costs (ยังไม่รู้ว่า P หรือ NP-Complete)
ผลงานวิจัยสำคัญ
- Karp (1961): Reduce to Integer Linear Programming → Exponential ใน n และ β
- Golin & Rote: O(n β²) Dynamic Programming (Top-down)
- Improved: Monotone Matrix Concepts (Monge Property, SMAWK Algorithm)
Theorems
THEOREM 1: Optimal Lopsided Trees สร้างได้ใน O(n β) Time (มากที่สุดสำหรับ β เล็ก เช่น Morse Codes)
THEOREM 2: มี Polynomial Time Approximation Scheme (PTAS) สำหรับ Optimal Lopsided Trees
สรุป
Lopsided Trees = Generalization ของ Huffman Trees สำหรับ Unequal Letter Costs
Exact Algorithm: O(n β) สำหรับ β เล็ก (Practical)
Approximation: PTAS มีอยู่สำหรับ General Case
Open Problem: Polynomial-time Exact Algorithm สำหรับ General α, β?
