فهرست ارائه‌های پژوهشی

مقالات ارائه‌شده به عنوان پروژه‌ی پژوهشی درس الگوریتم‌های تقریبی در این صفحه فهرست شده‌اند.

نیم‌سال اول ۱۴۰۳-۱۴۰۲

  • Habib Feli: Stochastic Minimum Vertex Cover in General Graphs: a 3/2-Approximation. By M. Derakhshan, N. Durvasula, and N. Haghtalab, STOC 2023.
  • Mohsen Ghorbani: Parameterized Approximation Scheme for Biclique-free Max k-Weight SAT and Max Coverage. By P. Jain et al., SODA 2023.
  • Seyedeh Zahra Seyed Fatehi: An LP-based approximation algorithm for the generalized traveling salesman path problem. By Jian Sun, Gregory Gutin, and Ping Li. COCOA 2021.
  • Mahdi Jafari: Approximation Algorithms for Steiner Tree Augmentation Problems. By R. Ravi, Weizhong Zhang, and Michael Zlatin, SODA 2023.
  • Hamid Piryayee: Clustering with neighborhoods. By H. Huang, G. Klimenko, and B. Raichel. ISAAC 2021.
  • Zahra Maleki: Almost Tight Approximation Algorithms for Explainable Clustering. By H. Esfandiari, V. S. Mirrokni, S. Narayanan, SODA 2022.
  • Mehran Zafari: Reducing Path TSP to TSP. By Vera Traub, Jens Vygen and Rico Zenklusen, SODA 2020.
  • Mohammad Cheraghi: Some Results on Approximability of Minimum Sum Vertex Cover. By Aleksa Stanković, APPROX 2022.
  • Hamid Naghizadeh: On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. By P. Afshani et al., SoCG 2022.
  • Ebrahim Koohi: Approximation Algorithms for Demand Strip Packing. By W. Gálvez, F. Grandoni, A. Jabal Ameli and K. Khodamoradi, APPROX 2021.
  • Ali Mirzaei: A 3-Approximation Algorithm for Maximum Independent Set of Rectangles. By Gálvez, Khan, Mari, Mömke, Pittu, and Wiese, SODA 2022.
  • Ali Rabbani: A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties. By X. Liu, W. Li and J. Yang , APPROX 2023.
  • Sajad Maleki: Probabilistic Metric Embedding via Metric Labeling. By K. Munagala, G. S. Sankar, and E. Taylor, APPROX 2023.

نیم‌سال اول ۱۴۰۲-۱۴۰۱

  • Homayoun Sadeghi & Iman Moghadari: An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem. By Karlin, Klein, Oveis Gharan, and Zhang, STOC 2022.
  • Amirhossein Mohammadpour & Hamid Piryayee: A 3-Approximation Algorithm for Maximum Independent Set of Rectangles. By Gálvez, Khan, Mari, Mömke, Pittu, and Wiese, SODA 2022.
  • Mostafa Montazri & Shima Rezai: Approximate Dynamic Balanced Graph Partitioning. By Racke, Schmid, and Zabrodin, SPAA 2022.
  • Hamid Naghizadeh: Approximation Algorithms for Demand Strip Packing. By Gálvez, Grandoni, Jabal Ameli, and Khodamoradi, APPROX 2021.
  • Mohsen Mohammadi & Saman Hadian: Approximation Schemes for Clustering with Outliers. By Friggstad, Khodamoradi, Rezapour, and Salavatipour, SODA 2018.

نیم‌سال اول ۱۴۰۰-۱۳۹۹

  • Mehran Moeini Jam: Maximizing Throughput in Flow Shop Real-Time Scheduling. By Ben Yamin, Li, Sarpatwar, Schieber and Shachnai, APPROX 2020.
  • Mohammad Rostami: 2-Approximating Feedback Vertex Set in Tournament. By Lokshtanov, Misra, Mukherjee, and Panolan, SODA 2020.
  • Mojtaba Fayaz-Bakhsh: How to Cut a Ball Without Separating: Improved Approximations for Length Bounded Cut. By Kolman and Chlamtác, APPROX 2020.
  • Mohammad Hadi Asadi: Approximate Maximum Matching in Random Streams. By Farhadi, Hajiaghayi, Mah, Rao, and Rossi, SODA 2020.
  • Ali Hatamshoar: A nearly 5/3-approximation FPT algorithm for min-k-cut. By Kawarabayashi and Lin, SODA 2020.
  • Mohammad Nakhaei: Approximation Algorithms for Finding Maximum Induced Expanders, By Oveis Gharan and Rezaei, SODA 2017.
  • Jafar Gholamzadeh: Approximating Requirement Cut via a Configuration LP. By Schwartz and Sharoni, APPROX 2020.
  • MohammadHossein Azizipour: An almost 2-approximation for all-pairs of shortest paths in subquadratic time. By Akav and Roditty, SODA 2020.
  • Erfan Valoubian: Approximating LCS in Linear Time: Beating the √n Barrier. By Hajiaghayi, Seddighin, Seddighin, and Sun, SODA 2019.
  • Seyyed Amirmahdi Mirfakhar: LP-based approximation for personalized reserved prices. By Derakhshan, Golrezaei, and Paes, EC 2019.
  • Sayed Mohammad Amin Khodaee: Fast LP-based Approximations for Geometric Packing and Covering Problems. By Chekuri, Har-Peled, and Quanrud, SODA 2020.
  • Mohammad Ahmadimehr: Streaming Complexity of SVMs. By Andoni, Burns, Li, Mahabadi, and Woodruff, APPROX 2020.
  • Niloofar Arazkhani: A Constant Factor Approximation for Capacitated Min-Max Tree Cover. By Das, Jain and Kumar, APPROX 2020.
  • Negar Sakhaei: Parameterized Complexity and Approximability of Directed Odd Cycle Transversal. By Lokshtanov, Ramanujan, Saurabh, and Zehavi, SODA 2020.
  • Mohammadreza Daneshvaramoli: Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. By Assadi, Kol, Saxena, and Yu, FOCS 2020.
  • Amir Hossein Maleki: PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching. Gupta, Krishnaswamy, and Sandeep, APPROX 2020.

نیم‌سال اول ۹۹-۱۳۹۸

  • Peyman Jabbarzade: Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence. By Hajiaghayi, Seddighin, and Sun, SODA 2019.
  • Mohammad Javad Eslami Bidgoli: A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees. By Amariah Becker, APPROX 2018.
  • Mohammad Ansari: Coloring in graph streams. By Bera and Ghosh. ArXiv 2018.
  • Emad Hedayati: Covering a tree with rooted subtrees: parameterized and approximation algorithms. By Chen and Marx, SODA 2018.
  • Parisa Zarei: (1 + ε)-approximate incremental matching in constant deterministic amortized time. By Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon, SODA 2019.
  • Farehe Soheil: Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs. By Bateni, Farhadi, and Hajiaghayi, SODA 2019.
  • Alireza Omidi: A tight sqrt(2)-approximation for linear 3-cut. By Berczi, Chandrasekaran, Kiraly, and Madan, SODA 2018.
  • Mojtaba Ostovari: 1 + ε approximation of tree edit distance in quadratic time. By Boroujeni, Ghodsi, Hajiaghayi, and Seddighin, STOC 2019.
  • Ali Mohammadi: On the cost of essentially fair clusterings. By Bercea et al. APPROX 2019.
  • Fatemeh Golchin: Preconditioning for the Geometric Transportation. By Boris Khesin, Nikolov, and Paramonov, SoCG 2019.
  • Koosha Jaferian: Finding Fair and Efficient Allocations. By Barman, Krishnamurthy, and Vaish, SODA 2018.

نیم‌سال دوم ۹۸-۱۳۹۷

  • Amir Malekzadeh: A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs. By Glencora Borradaile and Baigong Zheng, APPROX 2017.
  • Sina Farahzad: Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations. By Chandra Chekuri, and Shalmoli Gupta, APPROX 2018.
  • Hossein Naderi: A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem. By Svensson, Tarnawski, and Végh, STOC 2018.
  • Mohammad Reza Kasnavi: Semi-Direct Sum Theorem and Nearest Neighbor under `∞. By Mark Braveman and Young Kun Ko, APPROX 2018.
  • Amir Hossein Abiri: Approximate pure Nash equilibria in weighted congestion games. By Hansknecht, Klimm, and Skopalik, APPROX 2014.
  • Mohammad Aletaha: Simple greedy 2-approximation algorithm for the maximum genus of a graph. By Kotrbcık & Skoviera, SODA 2019.
  • Shervin Naseri: An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity. By Hao-Ting Wei, Wing-Kai Hon and Paul Horn, APPROX 2018.
  • Hossein Azizinaghsh: Improved Approximation Algorithm for Two-Dimensional Bin Packing. By Bansal and Khan, SODA 2014.
  • Mohammad Mahdi Habibollahi: Approximation Algorithms for Parallel Machine Scheduling with Speed-Up Resources, By Chen, Ye, and Zhang, APPROX 2016.
  • Soroush Ebadian: Approaching 3/2 for the $s$-$t$-path TSP. By Traub and Vygen, SODA 2018.
  • Arash Beikmohammadi: Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems. By Agrawal, Lokshtanov, Misra, Saurabh, and Meirav Zehavi, APPROX 2018.
  • Seyyed Mohammad Hosseini: Deterministic Algorithms for Submodular Maximization Problems. By Niv Buchbinder and Moran Feldman, SODA 2016.
  • Mohammad Reza Lotfi: A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees. By Amariah Becker, APPROX 2018.

نیم‌سال دوم ۹۷-۱۳۹۶

  • Hannaneh Akrami & Dorna Abdolazimi: A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem. By Svensson, Tarnawski and Végh, STOC 2018.
  • Hassan Nikaein & Reza Ahangarpour: A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy. By Halman, Approx 2016.
  • Mahdi Ramezani & Hamid Miri: A (2 + ϵ)-approximation for Maximum Weight Matching in the Semi-Streaming Model. By Paz and Shcwartzman. SODA 2017.
  • Faezeh Motiei & Leyla Biabani: Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. By Bhattacharya, Chakrabarty, and Henzinger, ICPO 2017.
  • Mohamad Latifian & Mohamad Zabolian: Revisiting Connected Dominating Sets: An Optimal Local Algorithm? By Khuller and Yang, Approx 2016.
  • Iliad Ramezani & Seyed khashayar Gatmiry: Improved Bounds in Stochastic Matching and Optimizations. By Baveja, Chavan, Nikiforov, Srinivasan, and Xu, Approx 2015.
  • MohammadJavad Hajialikhani & Nima Afshar: The Densest k-Subhypergraph Problem. By Chlamtác, Dinitz, Konrad, Kortsarz, and Rabanca, APPROX 2016.
  • Jalal Ahmadi: A linear time approximation scheme for computing geometric maximum k-star. By Wang and Hu, Global Optimization 2013.

نیم‌سال دوم ۹۶-۱۳۹۵

  • Ali Mostafavi & Mohammad Rasooli: Approximating k-center in planar graphs. By David Eisenstat and Philip N. Klein, SODA 2014.
  • Yeganeh Alimohammadi & Rojin Rezvan: Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms. By Riley Murray, Samir Khuller, and Megan Chao, ESA 2016.
  • Peyman Fakharian: Non-Uniform Robust Network Design in Planar Graphs. David Adjiashvili, APPROX 2015.
  • Sadra Alimi & Mohammad Habibollahi: Improved Streaming Algorithms for Weighted Matching via Unweighted Matching. By Michael Crouch and Daniel M. Stubbs, APPROX 2014.
  • Pooya Shati & Ramtin Afshar: A (2+∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model. By Ami Paz and Gregory Schwartzman, SODA 2017.
  • Azadeh Mousavi & Elahe Panahi: Better Approximations for Tree Sparsity in Nearly-Linear Time. By Arturs Backurs, Piotr Indyk, and Ludwig Schmidt, SODA 2017.
  • Afrooz Vazifedan: Complexity and algorithms for the connected vertex cover problem in 4-regular graphs. By Yuchao Li, Zishen Yang, and Wei Wang, Applied Math 2017.
  • Arash Pourdamghani & Ali Asghar Gorzin: On the Configuration-LP of the Restricted Assignment Problem. By Jansen and Rohwedder, SODA 2017.
  • Maryam Gholamalitabar: A Bi-Criteria Approximation Algorithm for K-Means. By Makarychev, Makarychev, Sviridenko, and Ward, APPROX 2016.

نیم‌سال دوم ۹۵-۱۳۹۴

  • Khashayar Etemadi & Navid Saleh: Online Set Cover with Set Requests. By Bhawalkar, Gollapudi, and Panigrahi, APPROX 2014.
  • Mahsa Eftekhari & Simin Oraee: Approximation Algorithms for Generalized and Variable-Sized Bin Covering. By Hellwig and Souza, APPROX 2012.
  • Amir Azizi & Amir Hossein Mozzafari: Improved Approximation Algorithm for Two-Dimensional Bin Packing. By Bansal and Khan, SODA 2014.
  • ​Mina Dalirrooyfard & Mohammad Sadra Moradian: Minimizing maximum flow-time on related machines. By Bansal and Cloostermans, MAPSP 2015.
  • Amir Sharifzadeh & Parsoa Khorsand: A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees. By Arya and Mount. SODA 2016.
  • Sobhan Miryusefi & Reza Miraskarshahi: A Simple FPTAS for Counting Edge Covers. Lin, Liu, and Lu, SODA 2014.
  • Ali Lavasani & Mohammad Taheri: Approximation Algorithms for Minimum-Load k-Facility Location. By Ahmadian et el., Approx 2014.
  • Mohammad Reza Bahrami & Vahid Reza Afreshte: Better Approximation Algorithms for the Graph Diameter. By Chechik et al., SODA 2014.
  • Amirhosein Rajabi & Mojtaba Amirabadian: Approximating independent sets in sparse graphs. By Nikhil Bansal, SODA 2015.
  • Sina Hamidian Shoormasti: A 9/7-Approximation Algorithm for Graphic TSP in Cubic Bipartite Grphs. By Karp and Ravi, APPROX 2014.

نیم‌سال دوم ۹۴-۱۳۹۳

  • Emad Aghajani & Maryam Rezaiee: Deliver or Hold: Approximation Algorithms For the Periodic Inventory Routing Problem. By Fukunaga, Nikzad and Ravi, APPROX 2014.
  • Mobin Yahyazadeh & Hadi Khodabande: The Approximability of the Binary Paintshop Problem. By Gupta et al., APPROX 2013.
  • Kooshan Abedian & Hamed Hosseinpour: A Distributed Algorithm for Approximate Mobile Sensor Coverage. By Ezra, Zengy, and Gaoy, CCCG 2014.
  • Sina Jafarzadeh & Javad Seyyedi: A Constant-Factor Approximation for Multi-Covering with Disks. By Bhowmick, Varadarajan, and Xue, SoCG 2013.
  • Reza Shojaee & Mohammad-Sadegh Borooni: Approximation Algorithms for Minimum-Load k-Facility Location. By Ahmadian, Behsaz, Friggstad, Jorati, Salavatipour, and Swamy, APPROX 2014.
  • Zahra Ekhtiari & Saba Esnaashari: Capacitated Network Design on Undirected Graphs. by Chakrabarty, Krishnaswamy, ShiLi, and Narayanan, APPROX 2013.
  • Mohammad Motiei & Sahand Mozaffari: Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching. By Crouch and Stubbs, APPROX 2014.
  • Maryam Chahian & Zahra Momtazian: Network Design with Coverage Costs. By Barman, Chawla, and Umboh, APPROX 2014.
  • Kian Mirjalali & Seyed Abbas Hosseini: Approximating Minimum Linear Ordering Problems. By Iwata, Tetali, and Tripathi, APPROX 2012.
  • Amin Sabzmakan & Seyed Ali Osia: The Online Stochastic Generalized Assignment Problem. By Alaei, Hajiaghayi and Liaghat, Approx 2013.
  • Shahlla Naseri & Amir Keramatian: Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. By Feldman, Schmidt, and Sohler, SODA 2013.
  • Sina Yazdanbod & Rezvan Sherkati: Approximating Full Steiner Tree in a Unit Disk Graph. By Biniaz, Maheshwari, and Smid, CCCG 2014.
  • Golnaz Taheri & Mahmood Shirazi: Online Set Cover with Set Requests. By Bhawalkar, Gollapudi, and Panigrahi, APPROX 2014.

نیم‌سال دوم ۹۲-۱۳۹۱

  • Rahmtin Rotabi: An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem. By Chandra Chekuri and Martin Pal, APPROX 2006.
  • AmirMahdi AhmadiNejad: O(1)-approximations for maximum movement problems. By Piotr Berman, Erik D. Demaine, and Morteza Zadimoghaddam. APPROX 2011.
  • Mina Tahmasbi: Prize-Collecting Survivable Network Design in Node-Weighted Graphs. By Chandra Chekuri, Alina Ene, and Ali Vakilian, APPROX 2012.
  • Mosen Abbasi: Approximation Algorithms for Variable-Sized and Generalized Bin Covering. By Matthias Hellwig and Alexander Souza, APPROX 2012.
  • Hamed Dastangoo: Maximum independent set of rectangles. By Chalermsook, Parinya, and Julia Chuzhoy, SODA 2009.
  • Ahmad Boorghany: Approximating the closest vector problem using an approximate shortest vector oracle. By Dubey Chandan, and Thomas Holenstein, APPROX 2011.
  • Misaq Saadat: Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs. By Piotr Berman, Grigory Yaroslavtsev, APPROX 2012.
  • Farhad Shahmohammadi: Maximum Matching in Semi-streaming with Few Passes. By Christian Konrad, Frédéric Magniez and Claire Mathieu, APPROX 2012.
  • Saman Naderi Parizi: Two approximation algorithms for ATSP with strengthened triangle inequality. By Lukasz Kowalik and Marcin Mucha, WADS 2009.
  • Mohammad Mahdi Amirian: New and Improved Bounds for the Minimum Set Cover Problem. By Rishi Saket and Maxim Sviridenko, APPROX 2012.

نیم‌سال دوم ۹۱-۱۳۹۰

  • Hajar Naji: The Price of Being Near-Sighted. By Kuhn, Moscibroda, and Wattenhofer. SODA 2006.
  • Mohammad Javad Rezayee Seraji: Approximating the girth. By Roditty and Tov. SODA 2011.
  • Pooya Zafar Asadollahpoor: An almost O(log k)-approximation for k-connected subgraphs. By Nutov. SODA 2009.
  • Fatemeh Keshavarz: A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs. By Borradaile, Kenyon-Mathieu, and Klein. SODA 2007.
  • Pouria Alimirzaei: Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs. By Christiano et al. STOC 2011.
  • Mahmood Alimohamadi: A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. By Borradaile, Klein, and Mathieu. FOCS 2009.
  • Marjan Adeli: A Constant-Factor Approximation Algorithm for TSP with Neighborhoods in the Plane. By Mitchell. SoCG 2010.
  • Salma Sadat Mahdavi: Parameterized Approximation Scheme for the Multiple Knapsack Problem. By Jansen. SODA 2009.
  • Mohammad Shadravan: An Improved LP-based Approximation for Steiner Tree. By Byrka, Grandoni, Rothvob, and Sanita. STOC 2010.
  • Omid Gheibi: A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover. By Bansal, Gupta, and Krishnaswamy. SODA 2010.
  • Mehdy Roayaei: An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods. By Asadpour and Saberi. STOC 2007.
  • Ehsan Zare: Approximating Maximum Weight Matching in Near-linear Time. By Duan and Pettie. FOCS 2010.
  • Hamid Homapour: A Dynamic Data Structure for Approximate Range Searching. By Mount and Park. SoCG 2011.
  • Hesam Monfared: Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP. By Archer, Bateni, Hajiaghayi, and Karloff. FOCS 2009.
  • Ali Narenji: Approximation Algorithms for Computing Partitions with Minimum Stabbing Number of Rectilinear and Simple Polygons. By Abam, Aronov, de Berg, and Khosravi. SoCG 2011.
  • Masood Seddighayn: A 1.875-Approximation Algorithm for the Stable Marriage Problem. By Iwama, Miyazaki, and Yamauchi. SODA 2007.