Table of Contents

My research interests are in design and analysis of algorithms and combinatorial optimization.

## Theory publications

- An Improved Approximation Algorithm for the s-t Path Movement Problem. (with Wattana Jindaluang, Jakarin Chawachat, Varin Chouvatut, Sanpawat Kantabutra)
*Chiang Mai J. Sci. 2017; 44(1) : 279-286, 2017* - Learning network structures from contagion. (with Adisak Supeesun)
*IPL.* - A simpler load-balancing algorithm for range-partitioned data in peer-to-peer systems. (with Jakarin Chawachat)
*NETWORKS, 66: 235–249. 2015* - The Non-uniform Bounded Degree Minimum Diameter Spanning Tree Problem with an Application in P2P Networking. (with Jakarin Chawachat and Wattana Jindaluang)
*IPL.* - An improved bound for multiple source-sink linear network coding. (with Munin Eamopas)
*JCSSE 2011.* - Faster Algorithms for Semi-Matching Problems. (with Bundit Laekhanukit and Danupon Nanongkai)
*ICALP 2010.* - Short proofs for online multiclass prediction on graphs. (with Boonserm Kijsirikul)
*IPL.* - Low congestion online routing and an improved mistake bound for online prediction of graph labeling. (with Boonserm Kijsirikul)
*manuscript.* - A Linear-Time Algorithm for the Multiple Gene Duplication Problem. (with Vacharapat Mettanant)
*The 12th National Computer Science and Engineering Conference (NCSEC'08).* - A better analysis of a Perceptron-based algorithm for multiclass importance weighted online learning
*JCSSE 2008.*(with Adisak Supeesun) - A running time analysis of an Ant Colony Optimization algorithm for shortest paths in directed acyclic graphs (with Nattapat Attiratanasunthron).
*IPL*. 105(3), pp 88-92, 2008. - Erratum to Constructing Multiclass Learners from Binary Learners: A Simple Black-Box Analysis of the Generalization Errors.
*ALT'05*(with Boonserm Kijsirikul)

Note: This paper contains errors. See the erratum. - Simple distributed algorithms for approximating Steiner trees
*COCOON'05*(with Parinya Chalermsook) - Approximate classification via earthmover metrics.
*SODA 04*(with Aaron Archer, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Eva Tardos) - A deterministic nearly linear-time algorithm for finding minimum cuts in planar graphs.
*SODA 04*(with Parinya Chalermsook and Danupon Nanongkai) - Multicommodity flows in planar graphs where all sinks are on the same face.
*Manuscript.*2003. (with Satish Rao) (see Ch.5 in thesis) - Algorithms for planar graphs.
*PhD Thesis.*(advisor: Satish Rao) - A tight bound on approximating arbitrary metrics by tree metrics.
*STOC 2003.*(with Satish Rao and Kunal Talwar) (journal version) - An improved approximation algorithm for the 0-extension problem.
*SODA 2003*(with Chris Harrelson, Satish Rao, Kunal Talwar) - Planar graphs, negative weight edges, shortest paths, and near linear time.
*FOCS 2001*(with Satish Rao) (.ps full version) - An improved VC-dimension bound for finding network failures
*Master project report*(advisor: Satish Rao)

## Applications of theory

- A faster algorithm for the tree containment problem for binary nearly stable phylogenetic networks
*JCSSE'15*(with Tanee Kumpijit and Attakorn Putwattana) - Comparison of recovery schemes to maximize restorable throughput in multicast networks
*J. Network and Computer Applications 35(3): 1106-1115 (2012)*(with Suwara Suraprasert) - Detecting and cleaning intruders in sensor networks.
*National Comp. Sci. and Eng. Conf. 2004 (NCSEC'04)*(with Poonna Yospanya, Bundit Laekhanukit, and Danupon Nanongkai) - POLL: multiclass classification from binary classifiers through random sampling.
*InTech'03.*(with Nithi Bunrupunthunad and Thanawin Rakthanmanon) - Approximating Aggregate Queries about Web Pages via Random Walks
*VLDB 2000.*(with Ziv Bar-Yossef, Alex Berg, Steve Chien, and Dror Weitz)

## Papers in Thai

- การปรับปรุงไซบิลการ์ดด้วยวิธีการตรวจสอบแบบท้องถิ่น (Improving SybilGuard using local verification).
*NCSEC 2007*(ทำกับ ณัฐวุฒิ กิจบุตราวัฒน์) - การเรียนรู้แบบออนไลน์สําหรับการจําแนกข้อมูลที่มีน้ำหนักความสําคัญ (Online learning for importance weighted classification).
*poster presentation NCSEC 2007.*(ทำกับ อดิศักดิ์ สุภีสุน)