Showing 2026 · cs.DSShow all
3 papers · 2 filters
cs.DS2026
On the Largest Cardinality Subset Sum
Deepak Bhati, Anubhav Dhar, Pranjal Dutta +2
We study Largest Cardinality Subset Sum (LCSS): given nonnegative integers and a target , compute a subset summing to with maximum cardinality. We also consider its all-…
cs.DS2026
Metric Planarity Testing is Hard
Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak +3
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for…
cs.DS2026
Faster Exponential Algorithms for Multi-Machine Scheduling Problems
Anubhav Dhar, Anita Dürr, Ahmed Ghazy +2
Minimizing the weighted completion times () and weighted number of tardy jobs () on multiple identical machines are two classical NP-har…