{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T11:08:08Z","timestamp":1756897688913,"version":"3.41.0"},"reference-count":99,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"German Federal Ministry for Education and Science","award":["13N16053"],"award-info":[{"award-number":["13N16053"]}]},{"name":"German Federal Ministry of Economic Affairs and Climate Action","award":["01MQ22006A"],"award-info":[{"award-number":["01MQ22006A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2025,7,31]]},"abstract":"<jats:p>\n            Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality assurance, as the enormous number of possible configurations makes it impractical to test each of them separately. This is where\n            <jats:italic toggle=\"yes\">t-wise interaction sampling<\/jats:italic>\n            can be used to systematically cover the configuration space and detect unknown feature interactions. Over the last two decades, numerous algorithms for computing small interaction samples have been studied, providing improvements for a range of heuristic results; nevertheless, it has remained unclear how much these results can still be improved.\n          <\/jats:p>\n          <jats:p>\n            We present a significant breakthrough: a fundamental framework, based on the mathematical principle of\n            <jats:italic toggle=\"yes\">duality<\/jats:italic>\n            , for combining near-optimal solutions with provable lower bounds on the required sample size. This implies that we no longer need to work on heuristics with marginal or no improvement, but can certify the solution quality by establishing a limit on the remaining gap; in many cases, we can even prove optimality of achieved solutions. This theoretical contribution also provides extensive practical improvements: Our algorithm SampLNS was tested on 47 small- and medium-sized configurable systems from the existing literature. SampLNS can reliably find samples of smaller size than previous methods in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(85\\%\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            of the cases; moreover, we can achieve and prove optimality of solutions for\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(63\\%\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            of all instances. This makes it possible to avoid cumbersome efforts of minimizing samples by researchers as well as practitioners, and substantially save testing resources for most configurable systems.\n          <\/jats:p>","DOI":"10.1145\/3712193","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T16:03:31Z","timestamp":1736784211000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["How Low Can We Go? Minimizing Interaction Samples for Configurable Systems"],"prefix":"10.1145","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1573-3496","authenticated-orcid":false,"given":"Dominik M.","family":"Krupke","sequence":"first","affiliation":[{"name":"Algorithms Division, TU Braunschweig, Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8511-7977","authenticated-orcid":false,"given":"Ahmad","family":"Moradi","sequence":"additional","affiliation":[{"name":"Algorithms Division, TU Braunschweig, Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0141-8594","authenticated-orcid":false,"given":"Michael","family":"Perk","sequence":"additional","affiliation":[{"name":"Algorithms Division, TU Braunschweig, Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6677-5090","authenticated-orcid":false,"given":"Phillip","family":"Keldenich","sequence":"additional","affiliation":[{"name":"Algorithms Division, TU Braunschweig, Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5485-0492","authenticated-orcid":false,"given":"Gabriel","family":"Gehrke","sequence":"additional","affiliation":[{"name":"TU Braunschweig, Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7077-7091","authenticated-orcid":false,"given":"Sebastian","family":"Krieter","sequence":"additional","affiliation":[{"name":"Institute of Software Engineering and Automotive Informatics (ISF), TU Braunschweig, Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8069-9584","authenticated-orcid":false,"given":"Thomas","family":"Th\u00fcm","sequence":"additional","affiliation":[{"name":"Institute of Software Engineering and Automotive Informatics (ISF), TU Braunschweig, Braunschweig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":false,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"additional","affiliation":[{"name":"Algorithms Division, TU Braunschweig, Braunschweig, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,7]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149119"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94144-8_9"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2017.2771562"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2993236.2993253"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/VACE.2017..8"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2993236.2993254"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10270-016-0569-2"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-022-09495-3"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CP.2021.12"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37521-7"},{"key":"e_1_3_1_12_2","first-page":"645","article-title":"On the solution of traveling salesman problems","author":"Applegate David","year":"1998","unstructured":"David Applegate, Robert Bixby, William Cook, and Vasek Chv\u00e1tal. 1998. On the solution of traveling salesman problems. Documenta Mathematica (1998), 645\u2013656.","journal-title":"Documenta Mathematica"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2015.7102591"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2014.43"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2660190.2662115"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409744"},{"key":"e_1_3_1_17_2","first-page":"51","volume-title":"Proceedings of the SAT Competition 2020 \u2013 Solver and Benchmark Descriptions","volume":"2020","author":"Biere Armin","year":"2020","unstructured":"Armin Biere, Katalin Fazekas, Mathias Fleury, and Maximillian Heisinger. 2020. CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling entering the SAT competition 2020. In Proceedings of the SAT Competition 2020 \u2013 Solver and Benchmark Descriptions. Tomas Balyo, Nils Froleyks, Marijn Heule, Markus Iser, Matti J\u00e4rvisalo, and Martin Suda (Eds.), Vol. B-2020-1, University of Helsinki, 51\u201353."},{"key":"e_1_3_1_18_2","first-page":"59","volume-title":"Proceedings of the International Conference on Software Engineering for Telecommunication Switching Systems (SETSS)","author":"Bowen Thomas F.","year":"1989","unstructured":"Thomas F. Bowen, Frank S. Dworack, Ching-Hua Chow, Nancy Griffeth, Gary E. Herman, and Yow-Jian Lin. 1989. The feature interaction problem in telecommunications systems. In Proceedings of the International Conference on Software Engineering for Telecommunication Switching Systems (SETSS). IEEE, Washington, DC, 59\u201362."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(02)00352-3"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2014.04.002"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.06.013"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.14416\/j.ijast.2014.05.001"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.605761"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2008.50"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400841103"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0518-7"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31095-9_40"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2021.110990"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/1788994.1789026"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3131151.3131152"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-010-9135-7"},{"key":"e_1_3_1_33_2","unstructured":"Gurobi Optimization LLC. 2023. Gurobi Optimizer Reference Manual. Retrieved from https:\/\/www.gurobi.com"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-018-9635-4"},{"key":"e_1_3_1_35_2","first-page":"237","volume-title":"Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications","author":"Hartman Alan","year":"2006","unstructured":"Alan Hartman. 2006. Software and hardware testing using combinatorial covering suites. In Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications. Martin Charles Golumbic and Irith Ben-Arroyo Hartman (Eds.), Vol. 34, Springer, 237\u2013266."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2430502.2430524"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09940-8_7"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2014.2327020"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491627.2491635"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564719.3568695"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382025.3414951"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3634713.3634716"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-015-9360-1"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24485-8_47"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2362536.2362547"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33666-9_18"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2019.00112"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2377816.2377817"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018457"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/1960275.1960284"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491459"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90098-8"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3106237.3106252"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/2451617.2451619"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3109729.3109751"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2205.15180"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377024.3377042"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3551349.3556938"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-006-7095-8"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/ECBS.2007.47"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3023956.3023961"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-35122-3_1"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2018.09.090"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSTW.2015.7107435"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3650212.3680309"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491627.2491646"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.769433"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/2884781.2884793"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-61443-4"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970322"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/3364452.33644558"},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336294.3342359"},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15579-6_14"},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/1944892.1944901"},{"key":"e_1_3_1_76_2","unstructured":"Laurent Perron and Vincent Furnon. 2024. OR-Tools. Retrieved from https:\/\/developers.google.com\/optimization\/"},{"key":"e_1_3_1_77_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2010.43"},{"key":"e_1_3_1_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442391.3442410"},{"key":"e_1_3_1_79_2","doi-asserted-by":"publisher","DOI":"10.1145\/3646548.3672589"},{"key":"e_1_3_1_80_2","doi-asserted-by":"publisher","DOI":"10.1145\/3336294.3336322"},{"key":"e_1_3_1_81_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91086-4_4"},{"key":"e_1_3_1_82_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2019.00032"},{"key":"e_1_3_1_83_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10270-015-0483-z"},{"key":"e_1_3_1_84_2","doi-asserted-by":"publisher","DOI":"10.1145\/2791060.2791074"},{"key":"e_1_3_1_85_2","first-page":"620","volume-title":"Proceedings of the International Conference on Logic for Programming, Artificial Intelligence, and Reasoning.","author":"Sharma Shubham","year":"2018","unstructured":"Shubham Sharma, Rahul Gupta, Subhajit Roy, and Kuldeep S. Meel. 2018. Knowledge compilation meets uniform sampling. In Proceedings of the International Conference on Logic for Programming, Artificial Intelligence, and Reasoning. EasyChair, 620\u2013636."},{"key":"e_1_3_1_86_2","doi-asserted-by":"publisher","DOI":"10.1145\/1985793.1985856"},{"key":"e_1_3_1_87_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28872-2_19"},{"key":"e_1_3_1_88_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11219-011-9152-9"},{"key":"e_1_3_1_89_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-022-10265-9"},{"key":"e_1_3_1_90_2","doi-asserted-by":"publisher","DOI":"10.1145\/2039239.2039242"},{"key":"e_1_3_1_91_2","doi-asserted-by":"publisher","DOI":"10.1145\/2580950"},{"key":"e_1_3_1_92_2","doi-asserted-by":"publisher","DOI":"10.1109\/SPLC.2011.53"},{"key":"e_1_3_1_93_2","doi-asserted-by":"publisher","DOI":"10.1145\/3233027.3233035"},{"key":"e_1_3_1_94_2","doi-asserted-by":"publisher","DOI":"10.1145\/2430502.2430515"},{"key":"e_1_3_1_95_2","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3264837"},{"key":"e_1_3_1_96_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276487"},{"key":"e_1_3_1_97_2","unstructured":"Huayao Wu Changhai Nie Justyna Petke Yue Jia and Mark Harman. 2019. A survey of constrained combinatorial testing. arXiv:1908.02480. Retrieved from http:\/\/arxiv.org\/abs\/1908.02480"},{"key":"e_1_3_1_98_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2015.7102599"},{"key":"e_1_3_1_99_2","doi-asserted-by":"publisher","DOI":"10.1002\/stv.430"},{"key":"e_1_3_1_100_2","doi-asserted-by":"publisher","DOI":"10.1145\/3611643.3616284"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3712193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T13:30:15Z","timestamp":1751376615000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":99,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,7,31]]}},"alternative-id":["10.1145\/3712193"],"URL":"https:\/\/doi.org\/10.1145\/3712193","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"type":"print","value":"1049-331X"},{"type":"electronic","value":"1557-7392"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2024-05-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-11","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}