{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:53:31Z","timestamp":1774626811447,"version":"3.50.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T00:00:00Z","timestamp":1631059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            Traditionally, capsule wardrobes are manually designed by expert fashionistas through their creativity and technical prowess. The goal is to curate minimal fashion items that can be assembled into several compatible and versatile outfits. It is usually a cost and time intensive process, and hence lacks scalability. Although there are a few approaches that attempt to automate the process, they tend to ignore the price of items or shopping budget. In this article, we formulate this task as a multi-objective budget constrained capsule wardrobe recommendation (\n            <jats:italic>MOBCCWR<\/jats:italic>\n            ) problem. It is modeled as a bipartite graph having two disjoint vertex sets corresponding to top-wear and bottom-wear items, respectively. An edge represents compatibility between the corresponding item pairs. The objective is to find a 1-neighbor subset of fashion items as a capsule wardrobe that jointly maximize compatibility and versatility scores by considering corresponding user-specified preference weight coefficients and an overall shopping budget as a means of achieving personalization. We study the complexity class of\n            <jats:italic>MOBCCWR<\/jats:italic>\n            , show that it is NP-Complete, and propose a greedy algorithm for finding a near-optimal solution in real time. We also analyze the time complexity and approximation bound for our algorithm. Experimental results show the effectiveness of the proposed approach on both real and synthetic datasets.\n          <\/jats:p>\n          <jats:p\/>","DOI":"10.1145\/3457182","type":"journal-article","created":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T15:31:23Z","timestamp":1631115083000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["A Graph Theoretic Approach for Multi-Objective Budget Constrained Capsule Wardrobe Recommendation"],"prefix":"10.1145","volume":"40","author":[{"given":"Shubham","family":"Patil","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Kharagpur, Kharagpur, West Bengal, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9773-776X","authenticated-orcid":false,"given":"Debopriyo","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kharagpur, Kharagpur, West Bengal, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4315-7329","authenticated-orcid":false,"given":"Shamik","family":"Sural","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kharagpur, Kharagpur, West Bengal, India"}]}],"member":"320","published-online":{"date-parts":[[2021,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep00196"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2306678"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313568"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.04.011"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401040"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 37th ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201914)","author":"Chen Jia","year":"2014","unstructured":"Jia Chen , Qin Jin , Shiwan Zhao , Shenghua Bao , Li Zhang , Zhong Su , and Yong Yu . 2014 . Does product recommendation meet its Waterloo in unexplored categories? No, price comes to help . In Proceedings of the 37th ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201914) . 667\u2013676. Jia Chen, Qin Jin, Shiwan Zhao, Shenghua Bao, Li Zhang, Zhong Su, and Yong Yu. 2014. Does product recommendation meet its Waterloo in unexplored categories? No, price comes to help. In Proceedings of the 37th ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201914). 667\u2013676."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4359(99)80100-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330652"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331184.3331254"},{"key":"e_1_2_1_10_1","article-title":"Neural feature-aware recommendation with signed hypergraph convolutional network","volume":"39","author":"Chen Xu","year":"2020","unstructured":"Xu Chen , Kun Xiong , Yongfeng Zhang , Long Xia , Dawei Yin , and Jimmy Xiangji Huang . 2020 . Neural feature-aware recommendation with signed hypergraph convolutional network . ACM Transactions Information Systems 39 , 1 (2020), Article 8, 22 pages. Xu Chen, Kun Xiong, Yongfeng Zhang, Long Xia, Dawei Yin, and Jimmy Xiangji Huang. 2020. Neural feature-aware recommendation with signed hypergraph convolutional network. ACM Transactions Information Systems 39, 1 (2020), Article 8, 22 pages.","journal-title":"ACM Transactions Information Systems"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331184.3331196"},{"key":"e_1_2_1_12_1","article-title":"Block-aware item similarity models for top-n recommendation","volume":"38","author":"Chen Yifan","year":"2020","unstructured":"Yifan Chen , Yang Wang , Xiang Zhao , Jie Zou , and Maarten De Rijke . 2020 . Block-aware item similarity models for top-n recommendation . ACM Transactions on Information Systems 38 , 4 (2020), Article 42, 26 pages. Yifan Chen, Yang Wang, Xiang Zhao, Jie Zou, and Maarten De Rijke. 2020. Block-aware item similarity models for top-n recommendation. ACM Transactions on Information Systems 38, 4 (2020), Article 42, 26 pages.","journal-title":"ACM Transactions on Information Systems"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2901299"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3343031.3350905"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401047"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0464-z"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"A data-driven approach to personalized bundle pricing and recommendation","volume":"22","author":"Ettl Markus","year":"2018","unstructured":"Markus Ettl , Pavithra Harsha , Anna Papush , and Georgia Perakis . 2018 . A data-driven approach to personalized bundle pricing and recommendation . Journal of Manufacturing & Service Operations Management 22 , 3 (2018), 1 \u2013 41 . Markus Ettl, Pavithra Harsha, Anna Papush, and Georgia Perakis. 2018. A data-driven approach to personalized bundle pricing and recommendation. Journal of Manufacturing & Service Operations Management 22, 3 (2018), 1\u201341.","journal-title":"Journal of Manufacturing & Service Operations Management"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401430"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32554-5_9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2019.2936742"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331184.3331245"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 2017 ACM International Conference on Multimedia (MM\u201917)","author":"Han Xintong","unstructured":"Xintong Han , Zuxuan Wu , Yu-Gang Jiang , and Larry S. Davis . 2017. Learning fashion compatibility with bidirectional LSTMs . In Proceedings of the 2017 ACM International Conference on Multimedia (MM\u201917) . 1078\u20131086. Xintong Han, Zuxuan Wu, Yu-Gang Jiang, and Larry S. Davis. 2017. Learning fashion compatibility with bidirectional LSTMs. In Proceedings of the 2017 ACM International Conference on Multimedia (MM\u201917). 1078\u20131086."},{"key":"e_1_2_1_23_1","unstructured":"Tong He and Yang Hu. 2018. FashionNet: Personalized outfit recommendation with deep neural network. arXiv:1810.02443.  Tong He and Yang Hu. 2018. FashionNet: Personalized outfit recommendation with deep neural network. arXiv:1810.02443."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 2018 ACM International Conference on Multimedia (MM\u201918)","author":"Hidayati Shintami Chusnul","year":"2018","unstructured":"Shintami Chusnul Hidayati , Cheng-Chun Hsu , Yu-Ting Chang , Kai-Lung Hua , Jianlong Fu , and Wen-Huang Cheng . 2018 . What dress fits me best? Fashion recommendation on the clothing style for personal body shape . In Proceedings of the 2018 ACM International Conference on Multimedia (MM\u201918) . 438\u2013446. Shintami Chusnul Hidayati, Cheng-Chun Hsu, Yu-Ting Chang, Kai-Lung Hua, Jianlong Fu, and Wen-Huang Cheng. 2018. What dress fits me best? Fashion recommendation on the clothing style for personal body shape. In Proceedings of the 2018 ACM International Conference on Multimedia (MM\u201918). 438\u2013446."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00748"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Wei-Lin Hsiao and Kristen Grauman. 2019. ViBE: Dressing for diverse body shapes. arXiv:1912.06697.  Wei-Lin Hsiao and Kristen Grauman. 2019. ViBE: Dressing for diverse body shapes. arXiv:1912.06697.","DOI":"10.1109\/CVPR42600.2020.01107"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"Human-centric clothing segmentation via deformable semantic locality-preserving network","volume":"30","author":"Ji Wei","year":"2019","unstructured":"Wei Ji , Xi Li , Fei Wu , Zhijie Pan , and Yueting Zhuang . 2019 . Human-centric clothing segmentation via deformable semantic locality-preserving network . IEEE Transactions on Circuits and Systems for Video Technology 30 , 12 (2019), 1 \u2013 12 . Wei Ji, Xi Li, Fei Wu, Zhijie Pan, and Yueting Zhuang. 2019. Human-centric clothing segmentation via deformable semantic locality-preserving network. IEEE Transactions on Circuits and Systems for Video Technology 30, 12 (2019), 1\u201312.","journal-title":"IEEE Transactions on Circuits and Systems for Video Technology"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304524"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461466.2461485"},{"key":"e_1_2_1_31_1","volume-title":"Knapsack Problems","author":"Kellerer Hans","unstructured":"Hans Kellerer , Ulrich Pferschy , and David Pisinger . 2004. Introduction to NP-completeness of knapsack problems . In Knapsack Problems . Springer , Berlin, Germany , 483\u2013493. Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Introduction to NP-completeness of knapsack problems. In Knapsack Problems. Springer, Berlin, Germany, 483\u2013493."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV\u201915)","author":"Kiapour M. Hadi","unstructured":"M. Hadi Kiapour , Xufeng Han , Svetlana Lazebnik , Alexander C. Berg , and Tamara L. Berg . 2015. Where to buy it: Matching street clothing photos in online shops . In Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV\u201915) . 3343\u20133351. M. Hadi Kiapour, Xufeng Han, Svetlana Lazebnik, Alexander C. Berg, and Tamara L. Berg. 2015. Where to buy it: Matching street clothing photos in online shops. In Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV\u201915). 3343\u20133351."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.31881\/TLR.2019.22"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1086\/209309"},{"key":"e_1_2_1_36_1","unstructured":"Kedan Li Chen Liu Ranjitha Kumar and David Forsyth. 2019. Using discriminative methods to learn fashion compatibility across datasets. arXiv:1906.07273.  Kedan Li Chen Liu Ranjitha Kumar and David Forsyth. 2019. Using discriminative methods to learn fashion compatibility across datasets. arXiv:1906.07273."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401080"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2017.2690144"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2906190"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2354409.2354954"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 38th International Conference on Research and Development in Information Retrieval(SIGIR\u201915)","author":"McAuley Julian","unstructured":"Julian McAuley , Christopher Targett , Qinfeng Shi , and Anton van den Hengel. 2015. Image-based recommendations on styles and substitutes . In Proceedings of the 38th International Conference on Research and Development in Information Retrieval(SIGIR\u201915) . 43\u201352. Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. 2015. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International Conference on Research and Development in Information Retrieval(SIGIR\u201915). 43\u201352."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13817-6_6"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Nilesh Pandey and Andreas Savakis. 2019. Poly-GAN: Multi-conditioned GAN for fashion synthesis. arXiv:1909.02165.  Nilesh Pandey and Andreas Savakis. 2019. Poly-GAN: Multi-conditioned GAN for fashion synthesis. arXiv:1909.02165.","DOI":"10.1016\/j.neucom.2020.07.092"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382764"},{"key":"e_1_2_1_45_1","volume-title":"LGVTON: A landmark guided approach to virtual try-on. arXiv:2004.00562.","author":"Roy Debapriya","year":"2020","unstructured":"Debapriya Roy , Sanchayan Santra , and Bhabatosh Chanda . 2020 . LGVTON: A landmark guided approach to virtual try-on. arXiv:2004.00562. Debapriya Roy, Sanchayan Santra, and Bhabatosh Chanda. 2020. LGVTON: A landmark guided approach to virtual try-on. arXiv:2004.00562."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/336992.337035"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3123266.3123314"},{"key":"e_1_2_1_49_1","volume-title":"Compatibility Modeling: Data and Knowledge Applications for Clothing Matching. Morgan & Claypool.","author":"Song Xuemeng","year":"2019","unstructured":"Xuemeng Song , Liqiang Nie , Yinglong Wang , and Gary Marchionini . 2019 . Compatibility Modeling: Data and Knowledge Applications for Clothing Matching. Morgan & Claypool. Xuemeng Song, Liqiang Nie, Yinglong Wang, and Gary Marchionini. 2019. Compatibility Modeling: Data and Knowledge Applications for Clothing Matching. Morgan & Claypool."},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 2019 IEEE International Conference on Computer Vision (ICCV\u201919)","author":"Tan Reuben","unstructured":"Reuben Tan , Mariya I. Vasileva , Kate Saenko , and Bryan A. Plummer . 2019. Learning similarity conditions without explicit supervision . In Proceedings of the 2019 IEEE International Conference on Computer Vision (ICCV\u201919) . 10373\u201310382. Reuben Tan, Mariya I. Vasileva, Kate Saenko, and Bryan A. Plummer. 2019. Learning similarity conditions without explicit supervision. In Proceedings of the 2019 IEEE International Conference on Computer Vision (ICCV\u201919). 10373\u201310382."},{"key":"e_1_2_1_51_1","unstructured":"Pongsate Tangseng Zhipeng Wu and Kota Yamaguchi. 2017. Looking at outfit to parse clothing. arXiv:1703.01386.  Pongsate Tangseng Zhipeng Wu and Kota Yamaguchi. 2017. Looking at outfit to parse clothing. arXiv:1703.01386."},{"key":"e_1_2_1_52_1","volume-title":"Approximation Algorithms","author":"Vazirani Vijay","unstructured":"Vijay Vazirani . 2003. Approximation Algorithms . Springer-Verlag , Berlin, Germany . Vijay Vazirani. 2003. Approximation Algorithms. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052568"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2754499"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 4th ACM Conference on Recommender Systems (RecSys\u201910)","author":"Xie Min","unstructured":"Min Xie , Laks V. S. Lakshmanan , and Peter T. Wood . 2010. Breaking out of the box of recommendations: From items to packages . In Proceedings of the 4th ACM Conference on Recommender Systems (RecSys\u201910) . ACM, New York, NY, 151\u2013158. Min Xie, Laks V. S. Lakshmanan, and Peter T. Wood. 2010. Breaking out of the box of recommendations: From items to packages. In Proceedings of the 4th ACM Conference on Recommender Systems (RecSys\u201910). ACM, New York, NY, 151\u2013158."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.407"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331184.3331242"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401150"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICWS.2017.127"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3337967"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00019"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609603"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457182","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:19Z","timestamp":1750191439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,8]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3457182"],"URL":"https:\/\/doi.org\/10.1145\/3457182","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,8]]},"assertion":[{"value":"2021-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}