Vardges Melkonian
Assistant Professor
Contact Information
- Department
of
- E-mail: vardges@math.ohiou.edu
- Office: Morton Hall 550
- Phone: (740)593-1279
Current and recent courses: Math 308 Discrete Mathematics
Math 306 Foundations of Mathematics I
Math 442/542 Theory Linear and Nonlinear Programming
Math 443/543 Mathematical Modeling and Optimization
Math 263b Calculus II
Math 250 Probability and Statistics I
CS 300/500N Introduction to Discrete Structures
Math 891 Applied and Computational Mathematics Seminar
Research Interests
Combinatorial Optimization
Mathematical Programming
Approximation Algorithms
Network Design Problems
Applications of Operations Research
The primary focus of my research is on the design and analysis of algorithms for fundamental problems in network, combinatorial optimization, approximation algorithms, linear and integer programming, and their applications to various problems. Most combinatorial optimization problems are NP-hard. I am interested in developing approximation algorithms for them, that is, algorithms which are fast and provide provably close-to-optimal solutions for the problems. My goal is to design algorithms which have both decent theoretical guarantees and good practical performance.
Some particular problems that I am working on now are the design of survivable networks, the asymmetric traveling salesman problem and the transportation in dynamic networks.
Survivable network design problems concern the design of those kind of networks that remain functional even if some of their elements (edges, nodes) are broken. Network design problems arise from many sources, including the design of various transportation systems (such as highways and mass-transit systems) as well as telephone and computer networks.
The traveling salesman problem (TSP) is one of the most famous problems in combinatorial optimization. Its goal is to find a minimum-cost tour which visits each node of the network exactly once. Despite the significant amount of research done on TSP, finding approximation algorithms for it (especially for the asymmetric version of the problem) remains one of the challenging directions in the area.
Another research direction concerns the transportation in dynamic networks. Dynamic networks are characterized by transit times and capacities on edges. The problems rising in dynamic networks have applications in shipping and military industries. A famous example is the evacuation problem.
Selected Publications
V. Melkonian
”LP-based
solution methods for asymmetric TSP "
Information Processing Letters, Vol.
101(6), 233-238, 2007.
V. Melkonian
"New
Primal-Dual Algorithms for Steiner Tree Problems"
Computers and Operations Research, Vol.
34(7), 2147-2167, 2007.
V. Melkonian
" Flows in dynamic networks with aggregate arc
capacities "
Information Processing Letters, Vol.
101(1), 30-35, 2007.
V. Melkonian and E . Tardos .
"Primal-Dual-Based
Algorithms for a Directed Network Design Problem"
INFORMS Journal on Computing, Vol.
17(2), 159-174, 2005.
R. Roundy, D. Chen, P. Chen, M. Cakanyildirim, M.B.
Freimer, V. Melkonian.
"Capacity-Driven
Acceptance of Customer Orders for a Multi-Stage Batch Manufacturing
System: Models and Algorithms"
IIE
Transactions on Scheduling and Logisitics, Vol.
37(12), 1093-1105, 2005.
V. Melkonian and E . Tardos .
"Algorithms for a Network Design Problem with Crossing Supermodular Demands"
Networks,
Vol. 43(4), 256-265, 2004.
Some links to Operations Research / Computer Science resources
|
|
|
|
|
|
|
|
|
Return to 
