فهرست ارائههای پژوهشی
مقالات ارائهشده به عنوان پروژهی پژوهشی درس الگوریتمهای تقریبی در این صفحه فهرست شدهاند.
نیمسال اول ۱۴۰۳-۱۴۰۲
- 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.