Approximation and Online Algorithms
20th International Workshop, WAOA 2022, Potsdam, Germany, September 8–9, 2022, Proceedings
Page
%P
-
Article
On Approximating Degree-Bounded Network Design Problems
Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph $$G=(V...
-
Book and Conference Proceedings
-
Article
Open AccessNew Tools and Connections for Exponential-Time Approximation
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer ...
-
Article
An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem
The minimum cost subset k-connected subgraph problem is a cornerstone problem in the area of network design with vertex connectivity requirements. In this problem, we are given a graph G=(V,E) with costs on edges...
-
Article
Routing Regardless of Network Stability
How effective are interdomain routing protocols, such as the border gateway protocol, at routing packets? Theoretical analyses have attempted to answer this question by ignoring the packets and instead focusing u...
-
Chapter and Conference Paper
Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
We consider the question of computing the strong edge coloring, square graph coloring, and their generalization to coloring the k th power of graphs. These prob...
-
Chapter and Conference Paper
Routing Regardless of Network Stability
How effective are interdomain routing protocols, such as the Border Gateway Protocol, at routing packets? Theoretical analyses have attempted to answer this question by ignoring the packets and instead focusing u...
-
Chapter and Conference Paper
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
In the k-arc connected subgraph problem, we are given a directed graph G and an integer k and the goal is the find a subgraph of minimum cost such that there are at least k-arc disjoint paths between any pair of ...
-
Chapter and Conference Paper
Non-redistributive Second Welfare Theorems
The second welfare theorem tells us that social welfare in an economy can be maximized at an equilibrium given a suitable redistribution of the endowments. We examine welfare maximization without redistributio...
-
Chapter and Conference Paper
An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
The minimum-cost subset k-connected subgraph problem is a cornerstone problem in the area of network design with vertex connectivity requirements. In this problem, we are given a graph G = (V,E) with costs on edg...
-
Chapter and Conference Paper
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing
We consider the Stackelberg shortest-path pricing problem, which is defined as follows. Given a graph G with fixed-cost and pricable edges and two distinct vertices s and t, we may assign prices to the pricable e...
-
Chapter and Conference Paper
Faster Algorithms for Semi-matching Problems (Extended Abstract)
We consider the problem of finding semi-matching in bipartite graphs which is also extensively studied under various names in the scheduling literature. We give faster algorithms for both weighted and unweighted ...
