Selected Publications

Algorithms and Discrete Applied Mathematics, Third International Conference, CALDAM 2017, Sancoale, Goa, India, February 16-18, 2017, Proceedings

Cumulative vehicle routing problems are a simplified model of fuel consumption in vehicle routing problems. Here we computationally study, an inexact approach for constructing solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation and is solved using column generation. The pricing subproblem is solved heuristically using dynamic programming. Simulation results show that a simple scalable strategy gives solutions with cost close to the lower bound given by the linear programming relaxation. We also give theoretical bounds on the integrality gap of the set cover formulation.
Discrete Applied Mathematics, In Press Corrected Proof, July 2016

We extend a previous model for scheduling commercial advertisements during breaks in television programming. The proposed extension allows differential weighting of conflicts between pairs of commercials. We formulate the problem as a capacitated generalization of the max k-cut problem in which the vertices of a graph correspond to commercial insertions and the edge weights to the conflicts between pairs of insertions. The objective is to partition the vertices into k capacitated sets to maximize the sum of conflict weights across partitions. We note that the problem is NP-hard. We extend a previous local-search procedure to allow for the differential weighting of edge weights. We show that for problems with equal insertion lengths and break durations, the worst-case bound on the performance of the proposed algorithm increases with the number of program breaks and the number of insertions per break, and that it is independent of the number of conflicts between pairs of insertions. Simulation results suggest that the algorithm performs well even if the problem size is small.
Operations Research 57(5): 1098–1105 (2009)

We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem, we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the minimum number of lines parallel to the x and y axes. We provide a 2-approximation algorithm, while the best known approximation ratio for this problem is O(logn). This algorithm is then extended to a 4-approximation algorithm for the rectilinear partitioning problem, which, given an mx × my array of nonnegative integers and positive integers v, h, asks to find a set of v vertical and h horizontal lines such that the maximum load of a subrectangle (i.e., the sum of the numbers in it) is minimized. The best known approximation ratio for this problem is 27. Our approximation ratio 4 is close to the best possible, as it is known to be NP-hard to approximate within any factor less than 2. The results are then extended to the d-dimensional space for d ≥ 2, where a d-approximation algorithm for the stabbing problem and a dd-approximation algorithm for the partitioning problem are developed.
Journal of Algorithms, 43(1): 138–152 (2002)

We compute the exact fractional chromatic number for several classes of monotone self-dual Boolean functions. We characterize monotone self-dual Boolean functions in terms of the optimal value of an LP relaxation of a suitable strengthening of the standard IP formulation for the chromatic number. We also show that determining the self-duality of a monotone Boolean function is equivalent to determining the feasibility of a certain point in a polytope defined implicitly.
Disc. Math. 309(4): 867–877 (2009)

We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.
Oper. Res. Lett. 41(6): 576-580 (2013)

Recent Posts

An emulator for Register Machine Our goal is to implement an emulator for a register machine using flex and bison. In the process we will illustrate a function that assigns numbers to programs, the von Neumann machine, and explain how to write self modifying code. Recall that a register machine has an unlimited number of registers and the following three instructions. HALT, stops the machine INC r j, increments the contents of register r, and moves to instruction number j.

CONTINUE READING

The third conference on algorithms and discrete applied mathematics CALDAM 2017 is being organized by the Department of Mathematics, BITS Pilani K.K. Birla Goa Campus from February 16 to 18, 2017. Invited Speakers at CALDAM 2017 are Sumit Ganguly, IIT Kanpur Martin C. Golumbic, University of Haifa Günter Rote, Freie Universitaet, Berlin Ola Svensson, EPFL Lausanne List of accepted papers is available here. The Program Committee Co-Chairs are N.

CONTINUE READING

Teaching

I have taught a variety of courses at the undergraduate and the graduate level. I have taught courses at Simon Fraser University, University of Lethbridge, TIFR Mumbai, IIT Delhi, IIT Ropar, IIT Mandi and at IIT BHU. Some of the courses that I have taught in the recent past are listed below.

  • Artificial Intelligence, CPSC 3750, Spring 2015
  • Approximation Algorithms, CPSC 5110, Fall 2016
  • Computer Networks CPSC 3780, Fall 2014, Fall 2016
  • Data Structures and Algorithms CPSC 3620, Spring 2017
  • Discrete Structures for Computer Science, CPSC 1820, Spring 2015, Spring 2016
  • Programming Languages CPSC 3740, Spring 2016, Spring 2017
  • Theory of Computation, CPSC 3630, Fall 2014

A select list of recent independent studies is below.

  • Approximation Algorithms, CPSC 5990, Spring 2015, Spring 2017
  • Mining of Massive Data Sets, CPSC 4990, Spring 2015
  • Practical Bioninformatics, CPSC 3990, Summer 2016
  • Quantum Computation, CPSC 5990, Summer 2016

Please visit https://moodle.uleth.ca for resources related to the current course offerings.

Contact

Graduate Students & Research Interns

It has been a pleasure working with several excellent students.

Name Degree Year
Peash Ranjan Saha M. Sc. cont.
Lazima Ansari M. Sc. cont.
Sharmin Akter M. Sc. cont.
Parijat Purohit M. Sc. cont. co-supervised with Dr. Benkoczi
Ram Dahal Ph. D. 2017 co-supervised with Dr. Benkoczi
Anamay Sarkar B. Tech 2016 MITACS Globalink Intern
Umair Arif M. Sc. 2017 co-supervised with Dr. Benkoczi
Kawsar Jahan M. Sc. 2015 co-supervised with Dr. Benkoczi, with TD Bank.
Anik Saha M. Sc. 2015 co-supervised with Dr. Hossain, with Aphelion.
Dr. Rishi Singh Ph. D. 2011-2012 IIT Ropar Now Assisant Professor at IIIT Allahabad.
Sangita Bhattacharjee M. Sc. 2010 Presently with the University of Lethbridge.
Tarikul Sabbir M. Sc. 2010 co-supervised with Dr. Benkoczi
Dr. Tauhid Islam M. Sc. 2009 Ph. D. from Queen’s University.
Dr. Salimur Choudhury M. Sc. 2008 Ph. D. from Queen’s University. Assistant Professor at Algoma U, Canada.
Dallas Thomas M. Sc. 2006 presently at Lethbridge Research Centre - Agriculture and Agri-Food Canada.
Elspeth Nickel M. Sc. 2005 co-supervised with Dr. Wismath.

Publications

I work on approximation algorithms. My research program has been supported by NSERC Discovery Grant since 2003. I am a member of the Optimization Research Group at the University of Lethbridge.

A list of publications as indexed by DBLP is below.