Publication
Anchor View Allocation for Collaborative Free Viewpoint Video Streaming
Related publications (140)
The Two Times Problem: Where Is the Problem?
Gruber et al. (2022) offered a framework how to explain "Physical time within human time", solving the 'two times problem: Here, I am asking whether such a problem exists at all. To question the question, I will appeal to neurobiological, evolutionary, and ...
Brill2024Approximation 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 ...
EPFL2023Results on Sparse Integer Programming and Geometric Independent Sets
An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...
EPFL2023Hands-on tasks make learning visible: a learning analytics lens on the development of mechanistic problem-solving expertise in makerspaces
Richard Lee Davis, Bertrand Roland Schneider
This study investigated the impact of participating in a year-long digital-fabrication course on high-school seniors' problem-solving skills, with a focus on problems involving mechanistic systems. The research questions centered on whether working in a ma ...
New York2023Discrete 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 ...
2022Minimum Cost Intervention Design for Causal Effect Identification
Negar Kiyavash, Sina Akbari, Seyed Jalal Etesami
Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...
PMLR2022Streaming 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 ...
EPFL2022Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Adam Teodor Polak, Alexandra Anna Lassota
We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...
Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022The double exponential runtime is tight for 2-stage stochastic ILPs
Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota
We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...
SPRINGER HEIDELBERG2022A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine
Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release time ...
ASSOC COMPUTING MACHINERY2021