Im, Sungjin; Moseley, Benjamin; Zhou, Rudy The matroid cup game. (English) Zbl 1525.91002 Oper. Res. Lett. 49, No. 3, 405-411 (2021). MSC: 91A05 05B35 68W27 90C27 91A80 91B32 PDFBibTeX XMLCite \textit{S. Im} et al., Oper. Res. Lett. 49, No. 3, 405--411 (2021; Zbl 1525.91002) Full Text: DOI
Antoniadis, Antonios; Im, Sungjin; Krishnaswamy, Ravishankar; Moseley, Benjamin; Nagarajan, Viswanath; Pruhs, Kirk; Stein, Clifford Hallucination helps: energy efficient virtual circuit routing. (English) Zbl 1448.68178 SIAM J. Comput. 49, No. 1, 37-66 (2020). MSC: 68M20 68M12 68W20 68W25 68W27 PDFBibTeX XMLCite \textit{A. Antoniadis} et al., SIAM J. Comput. 49, No. 1, 37--66 (2020; Zbl 1448.68178) Full Text: DOI
Fox, Kyle; Im, Sungjin; Kulkarni, Janardhan; Moseley, Benjamin Non-clairvoyantly scheduling to minimize convex functions. (English) Zbl 1430.90262 Algorithmica 81, No. 9, 3746-3764 (2019). MSC: 90B35 68W27 PDFBibTeX XMLCite \textit{K. Fox} et al., Algorithmica 81, No. 9, 3746--3764 (2019; Zbl 1430.90262) Full Text: DOI
Im, Sungjin; Kell, Nathaniel; Kulkarni, Janardhan; Panigrahi, Debmalya Tight bounds for online vector scheduling. (English) Zbl 1419.68218 SIAM J. Numer. Anal. 57, No. 1, 93-121 (2019). Reviewer: Frank Werner (Magdeburg) MSC: 68W27 68M20 68W40 90B35 PDFBibTeX XMLCite \textit{S. Im} et al., SIAM J. Numer. Anal. 57, No. 1, 93--121 (2019; Zbl 1419.68218) Full Text: DOI arXiv
Im, Sungjin; Kell, Nathaniel; Panigrahi, Debmalya; Shadloo, Maryam Online load balancing on related machines. (English) Zbl 1428.68395 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 30-43 (2018). MSC: 68W27 90B35 PDFBibTeX XMLCite \textit{S. Im} et al., in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 30--43 (2018; Zbl 1428.68395) Full Text: DOI arXiv
Im, Sungjin; Kulkarni, Janardhan; Munagala, Kamesh Competitive algorithms from competitive equilibria, non-clairvoyant scheduling under polyhedral constraints. (English) Zbl 1426.68309 J. ACM 65, No. 1, Article No. 3, 33 p. (2018). MSC: 68W27 68M20 90B35 91B52 PDFBibTeX XMLCite \textit{S. Im} et al., J. ACM 65, No. 1, Article No. 3, 33 p. (2018; Zbl 1426.68309) Full Text: DOI arXiv
Im, Sungjin; Kulkarni, Janardhan; Moseley, Benjamin; Munagala, Kamesh A competitive flow time algorithm for heterogeneous clusters under polytope constraints. (English) Zbl 1398.90050 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 19th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2016, and the 20th international workshop on randomization and computation, RANDOM 2016, Paris, France, September 7–9, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-018-7). LIPIcs – Leibniz International Proceedings in Informatics 60, Article 10, 15 p. (2016). MSC: 90B35 68W27 PDFBibTeX XMLCite \textit{S. Im} et al., LIPIcs -- Leibniz Int. Proc. Inform. 60, Article 10, 15 p. (2016; Zbl 1398.90050) Full Text: DOI
Im, Sungjin; Kulkarni, Janardhan; Munagala, Kamesh Competitive analysis of constrained queueing systems. (English) Zbl 1388.68018 Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 143, 13 p. (2016). MSC: 68M20 68W27 PDFBibTeX XMLCite \textit{S. Im} et al., LIPIcs -- Leibniz Int. Proc. Inform. 55, Article 143, 13 p. (2016; Zbl 1388.68018) Full Text: DOI
Avigdor-Elgrabli, Noa; Im, Sungjin; Moseley, Benjamin; Rabani, Yuval On the randomized competitive ratio of reordering buffer management with non-uniform costs. (English) Zbl 1422.68269 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 78-90 (2015). MSC: 68W20 68W27 90B35 PDFBibTeX XMLCite \textit{N. Avigdor-Elgrabli} et al., Lect. Notes Comput. Sci. 9134, 78--90 (2015; Zbl 1422.68269) Full Text: DOI
Im, Sungjin; Kulkarni, Janardhan; Munagala, Kamesh Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints. (English) Zbl 1315.90016 Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 313-322 (2014). MSC: 90B35 68W27 PDFBibTeX XMLCite \textit{S. Im} et al., in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 313--322 (2014; Zbl 1315.90016) Full Text: DOI
Im, Sungjin; Moseley, Benjamin; Pruhs, Kirk Online scheduling with general cost functions. (English) Zbl 1311.68195 SIAM J. Comput. 43, No. 1, 126-143 (2014). MSC: 68W27 90B35 PDFBibTeX XMLCite \textit{S. Im} et al., SIAM J. Comput. 43, No. 1, 126--143 (2014; Zbl 1311.68195) Full Text: DOI Link
Fox, Kyle; Im, Sungjin; Kulkarni, Janardhan; Moseley, Benjamin Online non-clairvoyant scheduling to simultaneously minimize all convex functions. (English) Zbl 1407.68562 Raghavendra, Prasad (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 16th international workshop, APPROX 2013, and 17th international workshop, RANDOM 2013, Berkeley, CA, USA, August 21–23, 2013. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8096, 142-157 (2013). MSC: 68W27 90B35 PDFBibTeX XMLCite \textit{K. Fox} et al., Lect. Notes Comput. Sci. 8096, 142--157 (2013; Zbl 1407.68562) Full Text: DOI
Im, Sungjin; Moseley, Benjamin; Pruhs, Kirk Online scheduling with general cost functions. (English) Zbl 1423.68610 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1254-1265 (2012). MSC: 68W27 90B35 PDFBibTeX XMLCite \textit{S. Im} et al., in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1254--1265 (2012; Zbl 1423.68610) Full Text: Link
Gupta, Anupam; Im, Sungjin; Krishnaswamy, Ravishankar; Moseley, Benjamin; Pruhs, Kirk Scheduling heterogeneous processors isn’t as easy as you think. (English) Zbl 1421.68248 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1242-1253 (2012). MSC: 68W27 68M20 90B35 PDFBibTeX XMLCite \textit{A. Gupta} et al., in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1242--1253 (2012; Zbl 1421.68248) Full Text: Link
Im, Sungjin; Moseley, Benjamin An online scalable algorithm for average flow time in broadcast scheduling. (English) Zbl 1295.68221 ACM Trans. Algorithms 8, No. 4, Article No. 39, 17 p. (2012). MSC: 68W27 68M10 68M20 68Q25 68W25 90B35 PDFBibTeX XMLCite \textit{S. Im} and \textit{B. Moseley}, ACM Trans. Algorithms 8, No. 4, Article No. 39, 17 p. (2012; Zbl 1295.68221) Full Text: DOI
Chekuri, Chandra; Im, Sungjin; Moseley, Benjamin Online scheduling to minimize maximum response time and maximum delay factor. (English) Zbl 1260.68470 Theory Comput. 8, Paper No. 7, 165-195 (2012). MSC: 68W27 68M20 PDFBibTeX XMLCite \textit{C. Chekuri} et al., Theory Comput. 8, Paper No. 7, 165--195 (2012; Zbl 1260.68470) Full Text: DOI
Cole, Daniel; Im, Sungjin; Moseley, Benjamin; Pruhs, Kirk Speed scaling for stretch plus energy. (English) Zbl 1245.90029 Oper. Res. Lett. 40, No. 3, 180-184 (2012). MSC: 90B35 90C47 PDFBibTeX XMLCite \textit{D. Cole} et al., Oper. Res. Lett. 40, No. 3, 180--184 (2012; Zbl 1245.90029) Full Text: DOI
Im, Sungjin; Wang, Yajun Secretary problems: laminar matroid and interval scheduling. (English) Zbl 1377.90075 Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1265-1274 (2011). MSC: 90C27 05B35 68Q25 68W27 90B35 PDFBibTeX XMLCite \textit{S. Im} and \textit{Y. Wang}, in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23--25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1265--1274 (2011; Zbl 1377.90075) Full Text: Link
Edmonds, Jeff; Im, Sungjin; Moseley, Benjamin Online scalable scheduling for the \(\ell_k\)-norms of flow time without conservation of work. (English) Zbl 1377.90026 Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 109-119 (2011). MSC: 90B35 68Q25 68W27 PDFBibTeX XMLCite \textit{J. Edmonds} et al., in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23--25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 109--119 (2011; Zbl 1377.90026) Full Text: Link
Im, Sungjin; Moseley, Benjamin An online scalable algorithm for minimizing \(\ell_k\)-norms of weighted flow time on unrelated machines. (English) Zbl 1377.90027 Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 95-108 (2011). MSC: 90B35 68Q25 68W27 PDFBibTeX XMLCite \textit{S. Im} and \textit{B. Moseley}, in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23--25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 95--108 (2011; Zbl 1377.90027) Full Text: Link
Chekuri, Chandra; Gal, Avigdor; Im, Sungjin; Khuller, Samir; Li, Jian; McCutchen, Richard; Moseley, Benjamin; Raschid, Louiqa New models and algorithms for throughput maximization in broadcast scheduling (extended abstract). (English) Zbl 1314.68406 Jansen, Klaus (ed.) et al., Approximation and online algorithms. 8th international workshop, WAOA 2010, Liverpool, UK, September 9–10, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-18317-1/pbk). Lecture Notes in Computer Science 6534, 71-82 (2011). MSC: 68W27 68M20 90B35 PDFBibTeX XMLCite \textit{C. Chekuri} et al., Lect. Notes Comput. Sci. 6534, 71--82 (2011; Zbl 1314.68406) Full Text: DOI
Im, Sungjin; Moseley, Benjamin An online scalable algorithm for average flow time in broadcast scheduling. (English) Zbl 1288.68286 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 1322-1333 (2010). MSC: 68W27 90B35 68W40 PDFBibTeX XMLCite \textit{S. Im} and \textit{B. Moseley}, in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1322--1333 (2010; Zbl 1288.68286)
Chekuri, Chandra; Im, Sungjin; Moseley, Benjamin Longest wait first for broadcast scheduling (extended abstract). (English) Zbl 1284.68678 Bampis, Evripidis (ed.) et al., Approximation and online algorithms. 7th international workshop, WAOA 2009, Copenhagen, Denmark, September 10–11, 2009. Revised papers. Berlin: Springer (ISBN 978-3-642-12449-5/pbk). Lecture Notes in Computer Science 5893, 62-74 (2010). MSC: 68W27 90B35 PDFBibTeX XMLCite \textit{C. Chekuri} et al., Lect. Notes Comput. Sci. 5893, 62--74 (2010; Zbl 1284.68678) Full Text: DOI
Chekuri, Chandra; Im, Sungjin; Moseley, Benjamin Minimizing maximum response time and delay factor in broadcast scheduling. (English) Zbl 1256.68018 Fiat, Amos (ed.) et al., Algorithms – ESA 2009. 17th annual European symposium, Copenhagen, Denmark, September 7–9, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-04127-3/pbk). Lecture Notes in Computer Science 5757, 444-455 (2009). MSC: 68M20 68W27 PDFBibTeX XMLCite \textit{C. Chekuri} et al., Lect. Notes Comput. Sci. 5757, 444--455 (2009; Zbl 1256.68018) Full Text: DOI