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

ประวัติ

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

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

งานวิจัยที่สนใจ: ด้าน 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'}$ เอกสารอ้างอิง [ ]

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 ทั้งหมดน้อยที่สุด

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

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

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

Movement Problem

Moblile Facility Location Problem

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