2 citations · 4 across the 16 of their papers we have counts for
19 papers
Incremental Submodular Maximization: Better Than Greedy
Marcin Bienkowski, Joakim Blikstad, Jarosław Byrka +3
We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of th…
Revisiting Diameter in Directed Graphs
Ben Bals, Joakim Blikstad, Daniel Dadush +2
The reachability diameter () of a directed graph is the maximum distance over all pairs where is reachable from . This notion is present in the def…
Deterministic Edge Coloring with few Colors in CONGEST
Joakim Blikstad, Yannic Maus, Tijn de Vos
As the main contribution of this work we present deterministic edge coloring algorithms in the CONGEST model. In particular, we present an algorithm that edge colors any -node g…
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, Jason Li +2
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time,…
Online Edge Coloring: Sharp Thresholds
Joakim Blikstad, Ola Svensson, Radu Vintan +1
Vizing's theorem guarantees that every graph with maximum degree admits an edge coloring using colors. In online settings - where edges arrive one at a time and must be…
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay +1
A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequ…
Efficient Matroid Intersection via a Batch-Update Auction Algorithm
Joakim Blikstad, Ta-Wei Tu
Given two matroids and over the same -element ground set, the matroid intersection problem is to find a largest common independent set, whose siz…
Deterministic Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan +1
We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially. The trivial greedy algorithm is -competitive, which is optimal for gra…
Maximum Flow by Augmenting Paths in Time
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak +1
We present a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time, whi…
Online Edge Coloring is (Nearly) as Easy as Offline
Joakim Blikstad, Ola Svensson, Radu Vintan +1
The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree can be edge colored (offline) using no more than colors (with being a tri…
Simple and Asymptotically Optimal Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan +1
We provide a simple online -edge-coloring algorithm for bipartite graphs of maximum degree under adversarial vertex arrivals on one side of the graph. Our…
Minimum Star Partitions of Simple Polygons in Polynomial Time
Mikkel Abrahamsen, Joakim Blikstad, André Nusser +1
We devise a polynomial-time algorithm for partitioning a simple polygon into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been…
Fast Algorithms via Dynamic-Oracle Matroids
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai +1
We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified" al…
Incremental -approximate dynamic matching in update time
Joakim Blikstad, Peter Kiss
In the dynamic approximate maximum bipartite matching problem we are given bipartite graph undergoing updates and our goal is to maintain a matching of which is large compa…
Nearly Optimal Communication and Query Complexity of Bipartite Matching
Joakim Blikstad, Jan van den Brand, Yuval Efron +2
We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AN…
Breaking O(nr) for Matroid Intersection
Joakim Blikstad
We present algorithms that break the -independence-query bound for the Matroid Intersection problem for the full range of ; where is the size of the ground set…
Breaking the Quadratic Barrier for Matroid Intersection
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay +1
The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids $\…
On the longest common subsequence of Thue-Morse words
Joakim Blikstad
The length of the longest common subsequence of the 'th Thue-Morse word and its bitwise complement is studied. An open problem suggested by Jean Berstel in 2006 is to fin…