45 citations · 92 across the 19 of their papers we have counts for
5 papers · 1 filter
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
Kim-Manuel Klein, Adam Polak, Lars Rohwedder
The starting point of this paper is the problem of scheduling jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy…
Bellman-Ford is optimal for shortest hop-bounded paths
Tomasz Kociumaka, Adam Polak
This paper is about the problem of finding a shortest - path using at most edges in edge-weighted graphs. The Bellman--Ford algorithm solves this problem in time,…
Product Portfolio Management in Competitive Environments
Samira Hossein Ghorban, Bardyaa Hesaam
Product diversity is one of the prominent factors for customers' satisfaction, while from the firms' perspective, the additional engineering costs required for product diversity sh…
Learning-Augmented Maximum Flow
Adam Polak, Maksym Zub
We propose a framework for speeding up maximum flow computation by using predictions. A prediction is a flow, i.e., an assignment of non-negative flow values to edges, which satisf…
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Alexandra Lassota, Aleksander Łukasiewicz, Adam Polak
We solve the Bin Packing problem in time, where is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the…