|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/4906
|
| タイトル: | Matrix Rounding under the L_p-Discrepancy Measure and Its Application to Digital Halftoning |
| 著者: | Asano, Tetsuo
Katoh, Naoki
Obokata, Koji
Tokuyama, Takeshi |
| キーワード: | approximation algorithm
digital halftoning
discrepancy
linear programming
matrix rounding
network flow
totally unimodular |
| 発行日: | 2003 |
| 出版者: | Society for Industrial and Applied Mathematics (SIAM) |
| 誌名: | SIAM Journal on Computing |
| 巻: | 32 |
| 号: | 6 |
| 開始ページ: | 1423 |
| 終了ページ: | 1435 |
| DOI: | 10.1137/S0097539702417511 |
| 抄録: | We study the problem of rounding a real-valued matrix into an integer-valued matrix to minimize an L_p-discrepancy measure between them. To define the L_p-discrepancy measure, we introduce a family F of regions (rigid submatrices) of the matrix and consider a hypergraph defined by the family. The difficulty of the problem depends on the choice of the region family F. We first investigate the rounding problem by using integer programming problems with convex piecewise-linear objective functions and give some nontrivial upper bounds for the L_p discrepancy. We propose “laminar family” for constructing a practical and well-solvable class of F. Indeed, we show that the problem is solvable in polynomial time if F is the union of two laminar families. Finally, we show that the matrix rounding using L_1 discrepancy for the union of two laminar families is suitable for developing a high-quality digital-halftoning software. |
| Rights: | Copyright (C) 2003 Society for Industrial and Applied Mathematics (SIAM). Tetsuo Asano, Naoki Katoh, Koji Obokata, and Takeshi Tokuyama, SIAM Journal on Computing, 32(6), 2003, 1423-1435. |
| URI: | http://hdl.handle.net/10119/4906 |
| 資料タイプ: | publisher |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| B3022.pdf | | 585Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
