Publication
Group-Sparse Model Selection: Hardness and Relaxations
Related publications (109)
Succinct ordering and aggregation constraints in algebraic array theories
We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring t ...
Elsevier Science Inc2024Approximation Algorithms for Allocation and Network Design
In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...
EPFL2023Certification of Bottleneck Task Assignment With Shortest Path Criteria
Maryam Kamgarpour, Tony Alan Wood
Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...
2023Streaming and Matching Problems with Submodular Functions
Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...
EPFL2022Discrete Optimal Transport with Independent Marginals is #P-Hard
Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen
We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...
2022Genomic Diversity of Torque Teno Virus in Blood Samples from Febrile Paediatric Outpatients in Tanzania: A Descriptive Cohort Study
Torque teno virus (TTV) is considered to be an ubiquitous member of the commensal human blood virome commonly reported in mixed genotype co-infections. This study investigates the genomic diversity of TTV in blood samples from 816 febrile Tanzanian childre ...
MDPI2022Impact of adherence to a lifestyle-integrated programme on physical function and behavioural complexity in young older adults at risk of functional decline: a multicentre RCT secondary analysis
Kamiar Aminian, Anisoara Ionescu
Context Long-term adherence to physical activity (PA) interventions is challenging. The Lifestyle-integrated Functional Exercise programmes were adapted Lifestyle-integrated Functional Exercise (aLiFE) to include more challenging activities and a behaviour ...
BMJ PUBLISHING GROUP2022Automating cutting planes is NP-hard
We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula F, It is -hard to find a CP refutation of F in time polynomial in the length of the shortest such refutation; and unless Gap-Hitting-Set admits a nontrivial algorithm, ...
ACM2021Bayesian Decision Making in Groups is Hard
We study the computations that Bayesian agents undertake when exchanging opinions over a network. The agents act repeatedly on their private information and take myopic actions that maximize their expected utility according to a fully rational posterior be ...
INFORMS2021Vessel scheduling with pilotage and tugging considerations
This paper considers vessel scheduling with pilotage and tugging constraints in berthing operations with channel restrictions at seaports. To our knowledge, pilotage and tugging requirements have not been simultaneously considered in the literature. This w ...
PERGAMON-ELSEVIER SCIENCE LTD2021