Author name cluster

Michael Zlatin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

FOCS Conference 2024 Conference Paper

The Online Submodular Assignment Problem

Daniel Hathcock
Billy Jin
Kalen Patton
Sherry Sarkar
Michael Zlatin

Online resource allocation is a rich and var-ied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp, Vazirani, and Vazirani. Since then, many variants have been studied, including AdWords, the generalized assignment problem (GAP), and online submodular welfare maximization. In this paper, we introduce a generalization of GAP which we call the submodular assignment problem (SAP). This generalization captures many online assignment problems, including all classical online bipartite matching problems as well as broader online combinatorial optimization problems such as online arboricity, flow scheduling, and laminar restricted allocations. We present a fractional algorithm for online SAP that is $(1-1/e)$ -competitive. Additionally, we study several integral special cases of the problem. In particular, we provide a $(1\ -1/e-\varepsilon){-}$ competitive integral algorithm under a small-bids assumption, and a $(1\ -1/e)$ -competitive integral algorithm for online submodular welfare maximization where the utility functions are given by rank functions of matroids. The key new ingredient for our results is the construction and structural analysis of a “water level” vector for polymatroids, which allows us to generalize the classic water-filling paradigm used in online matching problems. This construction reveals connections to submodular utility allocation markets and principal partition sequences of matroids.

Details

SODA Conference 2023 Conference Paper

Approximation Algorithms for Steiner Tree Augmentation Problems

R. Ravi 0001
Weizhong Zhang
Michael Zlatin

In the Steiner Tree Augmentation Problem (STAP), we are given a graph G = (V, E), a set of terminals R ⊆ V, and a Steiner tree T spanning R. The edges L: = E\E(T) are called links and have non-negative costs. The goal is to augment T by adding a minimum cost set of links, so that there are 2 edge-disjoint paths between each pair of vertices in R. This problem is a special case of the Survivable Network Design Problem, which can be approximated to within a factor of 2 using iterative rounding [13]. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular, we achieve an approximation ratio of (1. 5 + ε). To do this, we employ the Local Search approach of [24] for the Tree Augmentation Problem and generalize their main decomposition theorem from links (of size two) to hyper-links. We also consider the Node-Weighted Steiner Tree Augmentation Problem (NW-STAP) in which the non-terminal nodes have non-negative costs. We seek a cheapest subset S ⊆ V\R so that G[R ∪ S ] is 2-edge-connected. Using a result of Nutov [18], there exists an O (log | R |)-approximation for this problem. We provide an O (log 2 (| R |))-approximation algorithm for NW-STAP using a greedy algorithm leveraging the spider decomposition of optimal solutions.

Details