วัฒนา จินดาหลวง

ประวัติ

ชื่อ: วัฒนา จินดาหลวง

ชื่อเล่น: อ๋อย

งานวิจัยที่สนใจ: ด้าน approximation algorithms, graph theory, network design

ปัญหาที่เคยศึกษา

Metric Uncapacitated Facility Location Problem (UFL)

นิยามของปัญหา: ให้กราฟ G=(V,E) ที่แต่ละ edge e=(i,j) $\in$ E มีcost dij ที่ satisfy triangle inequality, set ของ cities C $\subseteq$ V, set ของ facilities F $\subseteq$ V, แต่ละ facility i $\in$ F มี cost ในการเปิดเป็น fi, แต่ละ city j $\in$ C มี cost ในการ connect กับ facility i ใน F เป็น dij ต้องการหา set F' $\subseteq$ F ที่ต้องเปิดและ assign แต่ละ city ให้กับบาง facility i'$\in$ F' โดยที่ ผลรวมของ cost ในการเปิดทุก ๆ facility ใน F' และ cost ในการ connect city j' เข้ากับ facility i'$\in$ F' น้อยที่สุด นั่นคือ minimize $\sum _{i'\in F'}{fi'}+\sum _{i'\in F',j'\in C}{di'j'}$ เอกสารอ้างอิง[STA1997][C1998][JV2001]

Online k-server Problem

นิยามปัญหา: กราฟ G=(V,E) ที่มี n โหนด, ระยะทางบน edge e=(u,v) ของกราฟ G (ใช้สัญลักษณ์ duv) โดยที่ duv เป็น metric, เครื่องบริการ k ตัว ที่ cover โหนดของ G ทั้ง k โหนดที่ต่างกัน, ลำดับของการร้องขอ (sequence of requests) ใช้สัญลักษณ์ $\sigma =\{\sigma _{1},\sigma _{2},\dots ,\sigma _{m}\}$ โดยที่ $\sigma _{i};1\leq i\leq m$ จะ ระบุโหนดของกราฟ G ที่ต้องการ service หมายเหตุ สำหรับปัญหา online k-server การตัดสินใจจะต้องทำทันทีเมื่อมีการร้องขอลำดับที่ i,$\sigma _{i}$, เข้ามาโดยที่ไม่เห็นลำดับการร้องขอในอนาคต นั่นคือไม่เห็นการร้องขอลำดับที่ j,$\sigma _{j},j>i$ คำตอบของปัญหา k-server ที่ต้องการคือลำดับของการตัดสินใจว่าจะย้าย server ตัวไหนเพื่อ serve ลำดับการร้องขอข้างต้นโดยให้ระยะทางในการย้าย server ทั้งหมดน้อยที่สุด

เอกสารอ้างอิง [MMS1990]

Metric k-center Problem

นิยามปัญหา: ให้ complete กราฟ G=(V,E), positive integer k, edge costs ที่ satisfy triangle inequality, ให้หา $S\subseteq V$ ที่ |S|=k และ minimize maximum distance จาก $v\in V$ ไปยัง vertex ที่ใกล้ที่สุดใน S นั่นคือ minimize $max_{v\in V}\{min_{u\in S}\{cost(u,v)\}\}$

เอกสารอ้างอิง [ ][ ]

Metric k-median Problem

นิยามปัญหา: เหมือน UFL แต่ facility $i\in F$ ไม่มี openning cost และ จำนวนของ facility ที่จะเปิดไม่เกิน k, |F'|$\leq$ k

เอกสารอ้างอิง [JV2001]

ปัญหาที่ศึกษาตอนนี้

Movement Problem

มีปัญหาที่ต้องการ move object (บน plane) แล้วต้องการให้หลังจากการ move แล้ว object มีคุณสมบัติ P บางอย่าง โดยที่ minimize objective cost function บางตัว จะ model ตำแหน่งที่ object อยู่และสามารถ move ไปได้ด้วย (directed/undirected)กราฟ G=(V,E) ที่ |V|=n verticies, model m objects ด้วย m pebbles ซึ่งอยู่บน vertex ต่าง ๆ ของกราฟ G, ตัวอย่างของ property P ที่ต้องการเช่น connectivity, directed connectivity, path between two certain vertices s and t, independent set, facility location เป็นต้น ตัวอย่างของ objective cost function เช่น maximum movement, total movement, number of movements เป็นต้น

นิยามต่าง ๆ จากงานวิจัย [DHMSOZ07]

1.configulation คือ function ที่ assign แต่ละ pebble ไปยัง vertex ของ V นั่นคือบอกว่า pebble ต่าง ๆ อยู่ตำแหน่ง(vertex)ไหนในกราฟบ้าง หมายเหตุ สามารถมี pebble มากกว่า 1 ตัวอยู่บน vertex เดียวกันได้

2.จะเรียก vertex v ที่มี pebble p อยู่ว่า vertex v ถูก occupy โดย pebble p

3.motion เป็นการ assign path $\pi (p)$ ในกราฟ G ให้กับแต่ละ pebble p โดยเริ่มต้นที่ initial configulation และจบที่บาง target vertex ซึ่งจะเรียกว่า target position (ดังนั้น pebble สามารถ move ได้ตาม edge บนกราฟเท่านั้น)

4.ความยาว |$\pi (p)$|ของ path คือ movement ของ pebble p

5.maximum movement ของ motion คือ maximum length ของ any path, total movement คือ ผลรวมของความยาวของทุก ๆ path, และ number of movements คือจำนวนของ path ที่มีความยาวไม่เป็นศูนย์

6.target ของ pebble จะ define target configulation

สรุปคือปัญหานี้ต้องการหา motion ที่ minimize objective cost function (1 ใน 3 ที่กล่าวไว้ข้างต้น) โดยที่ target configulation satisfying property P (บางอย่าง จากตัวอย่างข้างต้น)

Moblile Facility Location Problem

เป็นปัญหาที่รวม UFL กับ k-median เข้าด้วยกัน ถือว่าอยู่ในกลุ่มของ movement problem เหมือนกัน คือ มี pebble ที่ move ได้สองประเภท คือ facility และ city

นิยามปัญหา:

Wireless Sensor Network

(survey ไม่ได้ทำวิจัยที่เป็น application จริง ๆ)

เอกสารอ้างอิง

[MMS1990] Mark S. Manasse,Lyle A.McGeoch, and Daniel D Slestor;"Competitive Algorithms for Server Problems",1990.

[DHMSOZ07] Demaine, E.D., M. Hajiaghayi, H. Mahini, A. Sayedi-Roshkhar, S. Oveisgharan and M. Zadimoghaddam. 2007. Minimizing Movement. In ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Louisianna.

[STA1997]Shmoys, D.B., E. Tardos and K. Aardal. 1997. Approximation algorithms for facility location problems. pp. 265-274. In 29th ACM Symposium on Theory of Computing.

[C1998]Chudak, F.A. 1998. Improved approximation algorithms for uncapacitated facility location. IPCO VI. 1442: 180-194.

[JV2001]Jain, K. and V.V. Vazirani. 2001. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM. 48(2): 274-292.