CSCE-669 Computational Optimization (Spring 2024)

Instructor: Dr. Jianer Chen
Office:PETR 428
Phone:(979) 845-4259
Email:chen@cse.tamu.edu
Web: https://people.engr.tamu.edu/j-chen3/
Office hours:M&W 11:30 am-1:00 pm

Course Syllabus

Textbook
Jianer Chen: Introduction to Tractability and Approximability of Optimization Problems, Lecture Notes, Dept. Computer Science and Engineering, TAMU.

Additional Reading Materials
  • J. Chen, et al.: Linear-time algorithms with limited local resources, Information and Computation 289 (2022).
  • J. Chen, et al.: Streaming algorithms for graph k-matching with optimal or near-optimal update time, arXiv:2310.10815v1 [cs.DS] (2023).
  • H. Gabow: Data structures for weighted matching and extensions to b-matching and f-factors, ACM Transactions on Algorithms 14 (2018).
  • L. Chen, et al.: Almost-linear-time algorithms for maximum flow and minimum-cost flow, Communications of the ACM 66 (2023).
  • S.-H. Teng: Maximum flow through a network: a storied problem and a groundbreaking solution, Communications of the ACM 66 (2023).
  • N. Veldt: Growing a random maximal independent set produces a 2-approximate vertex cover, In Proc. 2024 Symposium on Simplicity in Algorithms (SOSA) (2024).
  • G. Wu, et al.: Scheduling two-stage jobs on multiple flowshops, Theoretical Computer Science 776 (2019).
  • J. Chen, et al.: Polynomial time approximation schemes and parameterized complexity, Discrete Applied Mathematics 155 (2007).
  • W. Tong, et al.: A polynomial time approximation scheme for parallel two-stage flowshops under makespan constraint, appeared in Theoretical Computer Science 922 (2022).
  • J. Dong, et al.: A polynomial time approximation scheme for an arbitrary number of parallel two-stage flow-shops, European Journal of Operational Research 281 (2020).
  • J. Chen and A. Miranda: A polynomial time approximation scheme for general multiprocessor job scheduling, SIAM Journal on Computing 31-1 (2001).
  • Ce Jin: 0-1 Knapsack in nearly quadratic time, arXiv:2308.04093v1 [cs.DS] (2023).

    • Course Progress
    Date Topics Lecture Notes Announcement
    Jan. 17 Introduction Chapter 1
    		Chapter 1(Introduction) has been posted
    Jan. 19 Graph matching Reading materials on graph matching are posted
    Jan. 22 Graph matching on general and weighted graphs Chapter 2
    		Chapter 2 (Graph Matching) has been posted
    Jan. 24 Recent research in graph matching algorithms References
    		References has been posted
    Jan. 26 Maximum flow algorithms Chapter 3
    		Chapter 3 (Maximum Flow) has been posted
    Jan. 29 Recent progress in maximum flow algorithms Reading materials on maximum flow are posted
    Jan. 31 Linear programming Chapter 4
    		Chapter 4 (Linear Programming) has been posted
    Feb. 2 NP-hard optimization problems Chapter 5
    		Chapter 5 (NP-hard Problems) has been posted
    Feb. 5 Polynomial-time reductions Homework Assignment #1 has been posted
    Feb. 7 Approximation algorithms for NP-hard problems
    Feb. 9 Approximation algorithms for Vertex Cover A new paper on Vertex Cover is posted
    Feb. 12 Examples: approximating Makespan and Knapsack Chapter 6
    		Chapter 6 (FPTAS) has been posted
    Feb. 14 Psuedo-polynomial time algorithms Reading materials on scheduling are posted.
    Feb. 16 Fully polynomial-time approximation schemes Homework #1 is due on Feb. 19.
    Feb. 19 FPTAS for Knapsack Project instruction is posted
    Feb. 21 FPTAS for c-Makespan Reading materials on FPTAS are posted
    Feb. 23 Strong NP-hardness
    Feb. 26 Bin-packing
    Feb. 28 Polynomial-time approximation schemes (PTAS)
    March 1 Maximum Independent-Set on planar graphs
    March 4 Optimizations on planar graphs
    March 6 More advanced techniques on planar graphs
    March 8 Approximating Metric TSP
    March 11-15 Spring Break
    March 18 PTAS on Euclidean TSP Chapter 7
    		Chapter 7 (PTAS) has been posted
    March 20 PTAS on Euclidean TSP (cont.) Homework Assignment #2 has been posted
    March 22 PTAS on Euclidean TSP (cont.) More reading papers have been posted
    March 25 Constant ratio approximations
    March 27 Christofides' algorithm for Metric-TSP Project proposals have been reviewed
    March 29 Reading day, no class
    April 1 2-SAT and Max-2SAT Chapter 8
    		Chapter 8 (APX) has been posted
    April 3 Johnson's algorithm for Max-SAT
    April 5 Survey on algorithms for SAT and Max-SAT The arts of satisfiability
    April 8 A randomized algorithm for Min-Cut
    April 10 Randomized algorithms for Max-SAT
    April 12 Improving the expected approximation ratios
    April 15 Derandomization-I Chapter 9 (Probablistic Methods) has been posted
    April 17 Derandomization-II
    April 19 Max-SAT: Linear program relaxation
    April 22 Approximating Max-Cut
    April 24 Max-Cut: Semidefinite program relaxation
    April 26 APX-hardness and E-reduction Chapter 9
    		Revised Chapter 9 has been posted

    Assignments
    (Assignments are due on the designated due dates at the beginning of the class)
    Assignment Due Date
    Homework #1 Feb. 19
    Homework #2 April 3
    Homework #3 April 24
    Project proposal March 25
    Course project April 29