Table of Contents
Theory publications
Applications of theory
Papers in Thai
My research interests are in design and analysis of algorithms and combinatorial optimization.
Theory publications
Learning Network Structures from Contagion
. (with Adisak Supeesun)
IPL.
An Improved Approximation Algorithm for the s-t Path Movement Problem
. (with Wattana Jindaluang, Jakarin Chawachat, Varin Chouvatut, Sanpawat Kantabutra)
Chiang Mai Journal of Science.
A simpler load-balancing algorithm for range-partitioned data in peer-to-peer systems
. (with Jakarin Chawachat)
Networks.
(
journal version
)
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.
(
journal version
in TALG)
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).
An $O(\log^2 k)$-approximation algorithm for the $k$-vertex connected spanning subgraph problem
(with
Bundit Laekhanukit
).
STOC'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)
An improved decomposition theorem for graphs excluding a fixed minor.
APPROX 03
. (with
Kunal Talwar
)
A tight bound on approximating arbitrary metrics by tree metrics.
STOC 2003.
(with
Satish Rao
and
Kunal Talwar
) (
journal version
)
The k-traveling repairman problem.
SODA 2003
. (with
Chris Harrelson
and
Satish Rao
)
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
An Improved Centralized Algorithm for Distance-Preserving Dominating Sets in Heterogeneous Wireless Sensor Networks
ICSEC'16
(with Attakorn Putwattana)
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.
(ทำกับ อดิศักดิ์ สุภีสุน)