Search

In the maximum independent set of convex polygons problem, we are given a set of $n$ convex polygons in the plane with the objective of selecting a maximum cardinality subset of non-overlapping polygons. Here we study a special case of the problem where the edges of the polygons can take at most $d$ fixed directions. We present an $8d/3$-approximation algorithm for this problem running in time $O((nd)^{O(d4^d)})$. The previous-best polynomial-time approximation (for constant $d$) was a classical $n^\varepsilon$ approximation by Fox and Pach [SODA'11] that has recently been improved to a $OPT^{\varepsilon}$-approximation algorithm by Cslovjecsek, Pilipczuk and W\k{e}grzycki [SODA '24], which also extends to an arbitrary set of convex polygons. Our result builds on, and generalizes the recent constant factor approximation algorithms for the maximum independent set of axis-parallel rectangles problem (which is a special case of our problem with $d=2$) by Mitchell [FOCS'21] and G\'{a}lvez, Khan, Mari, M\"{o}mke, Reddy, and Wiese [SODA'22]., Comment: To appear at SoCG 2024

Web requests are growing exponentially since the 90s due to the rapid development of the Internet. This process was further accelerated by the introduction of cloud services. It has been observed statistically that memory or web requests generally follow power-law distribution, Breslau et al. INFOCOM'99. That is, the $i^{\text{th}}$ most popular web page is requested with a probability proportional to $1 / i^{\alpha}$ ($\alpha > 0$ is a constant). Furthermore, this study, which was performed more than 20 years ago, indicated Zipf-like behavior, i.e., that $\alpha \le 1$. Surprisingly, the memory access traces coming from petabyte-size modern cloud systems not only show that $\alpha$ can be bigger than one but also illustrate a shifted power-law distribution -- called Pareto type II or Lomax. These previously not reported phenomenon calls for statistical explanation. Our first contribution is a new statistical {\it multi-core power-law} model indicating that double-power law can be attributed to the presence of multiple cores running many virtual machines in parallel on such systems. We verify experimentally the applicability of this model using the Kolmogorov-Smirnov test (K-S test). The second contribution of this paper is a theoretical analysis indicating why LRU and LFU-based algorithms perform well in practice on data satisfying power-law or multi-core assumptions. We provide an explanation by studying the online paging problem in the stochastic input model, i.e., the input is a random sequence with each request independently drawn from a page set according to a distribution $\pi$. We derive formulas (as a function of the page probabilities in $\pi$) to upper bound their ratio-of-expectations, which help in establishing O(1) performance ratio given the random sequence following power-law and multi-core power-law distributions.

This paper presents a new research direction for online Multi-Level Aggregation (MLA) with delays. In this problem, we are given an edge-weighted rooted tree $T$, and we have to serve a sequence of requests arriving at its vertices in an online manner. Each request $r$ is characterized by two parameters: its arrival time $t(r)$ and location $l(r)$ (a vertex). Once a request $r$ arrives, we can either serve it immediately or postpone this action until any time $t > t(r)$. We can serve several pending requests at the same time, and the service cost of a service corresponds to the weight of the subtree that contains all the requests served and the root of $T$. Postponing the service of a request $r$ to time $t > t(r)$ generates an additional delay cost of $t - t(r)$. The goal is to serve all requests in an online manner such that the total cost (i.e., the total sum of service and delay costs) is minimized. The current best algorithm for this problem achieves a competitive ratio of $O(d^2)$ (Azar and Touitou, FOCS'19), where $d$ denotes the depth of the tree. Here, we consider a stochastic version of MLA where the requests follow a Poisson arrival process. We present a deterministic online algorithm which achieves a constant ratio of expectations, meaning that the ratio between the expected costs of the solution generated by our algorithm and the optimal offline solution is bounded by a constant. Our algorithm is obtained by carefully combining two strategies. In the first one, we plan periodic oblivious visits to the subset of frequent vertices, whereas in the second one, we greedily serve the pending requests in the remaining vertices. This problem is complex enough to demonstrate a very rare phenomenon that ``single-minded" or ``sample-average" strategies are not enough in stochastic optimization., Comment: 37 pages, 3 figures

When launching new products, firms face uncertainty about market reception. Online reviews provide valuable information not only to consumers but also to firms, allowing firms to adjust the product characteristics, including its selling price. In this paper, we consider a pricing model with online reviews in which the quality of the product is uncertain, and both the seller and the buyers Bayesianly update their beliefs to make purchasing & pricing decisions. We model the seller's pricing problem as a basic bandits' problem and show a close connection with the celebrated Catalan numbers, allowing us to efficiently compute the overall future discounted reward of the seller. With this tool, we analyze and compare the optimal static and dynamic pricing strategies in terms of the probability of effectively learning the quality of the product.

We study a natural combinatorial pricing problem for sequentially arriving buyers with equal budgets. Each buyer is interested in exactly one pair of items and purchases this pair if and only if, upon arrival, both items are still available and the sum of the item prices does not exceed the budget. The goal of the seller is to set prices to the items such that the number of transactions is maximized when buyers arrive in adversarial order. Formally, we are given an undirected graph where vertices represent items and edges represent buyers. Once prices are set to the vertices, edges with a total price exceeding the buyers' budgets are evicted. Any arrival order of the buyers leads to a set of transactions that forms a maximal matching in this subgraph, and an adversarial arrival order results in a minimum maximal matching. In order to measure the performance of a pricing strategy, we compare the size of such a matching to the size of a maximum matching in the original graph. It was shown by Correa et al. [IPCO 2022] that the best ratio any pricing strategy can guarantee lies within $[1/2, 2/3]$. Our contribution to the problem is two-fold: First, we provide several characterizations of subgraphs that may result from pricing schemes. Second, building upon these, we show an improved upper bound of $3/5$ and a lower bound of $1/2 + 2/n$, where $n$ is the number of items.

We consider an online version of the geometric minimum hitting set problem that can be described as a game between an adversary and an algorithm. For some integers $d$ and $N$, let $P$ be the set of points in $(0, N)^d$ with integral coordinates, and let $\mathcal{O}$ be a family of subsets of $P$, called objects. Both $P$ and $\mathcal{O}$ are known in advance by the algorithm and by the adversary. Then, the adversary gives some objects one by one, and the algorithm has to maintain a valid hitting set for these objects using points from $P$, with an immediate and irrevocable decision. We measure the performance of the algorithm by its competitive ratio, that is the ratio between the number of points used by the algorithm and the offline minimum hitting set for the sub-sequence of objects chosen by the adversary. We present a simple deterministic online algorithm with competitive ratio $((4\alpha+1)^{2d}\log N)$ when objects correspond to a family of $\alpha$-fat objects. Informally, $\alpha$-fatness measures how cube-like is an object. We show that no algorithm can achieve a better ratio when $\alpha$ and $d$ are fixed constants. In particular, our algorithm works for two-dimensional disks and $d$-cubes which answers two open questions from related previous papers in the special case where the set of points corresponds to all the points of integral coordinates with a fixed $d$-cube.

We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA'19] showed that it is also W[1]-hard when parameterized by the size $k$ of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90{\textdegree} before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question. In this work, we make progress towards this goal by showing a PAS under the following assumptions: - both the box and all the input rectangles have integral, polynomially bounded sidelengths; - every input rectangle is wide -- its width is greater than its height; and - the aspect ratio of the box is bounded by a constant.Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.

This paper presents a new research direction for the Min-cost Perfect Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). In the original version of this problem, we are given an $n$-point metric space, where requests arrive in an online fashion. The goal is to minimise the matching cost for an even number of requests. However, contrary to traditional online matching problems, a request does not have to be paired immediately at the time of its arrival. Instead, the decision of whether to match a request can be postponed for time $t$ at a delay cost of $t$. For this reason, the goal of the MPMD is to minimise the overall sum of distance and delay costs. Interestingly, for adversarially generated requests, no online algorithm can achieve a competitive ratio better than $O(\log n/\log \log n)$ (Ashlagi et al., APPROX/RANDOM'17). Here, we consider a stochastic version of the MPMD problem where the input requests follow a Poisson arrival process. For such a problem, we show that the above lower bound can be improved by presenting two deterministic online algorithms, which, in expectation, are constant-competitive. The first one is a simple greedy algorithm that matches any two requests once the sum of their delay costs exceeds their connection cost, i.e., the distance between them. The second algorithm builds on the tools used to analyse the first one in order to obtain even better performance guarantees. This result is rather surprising as the greedy approach for the adversarial model achieves a competitive ratio of $\Omega(m^{\log \frac{3}{2}+\varepsilon})$, where $m$ denotes the number of requests served (Azar et al., TOCS'20). Finally, we prove that it is possible to obtain similar results for the general case when the delay cost follows an arbitrary positive and non-decreasing function, as well as for the MPMD variant with penalties to clear pending requests., Comment: 34 pages, 7 figures, accepted at AAMAS'23

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.

We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [2021] obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs), without intersecting certain special horizontal line segments called fences. In this paper, we present a $(2+\epsilon)$-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 6. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to $2+\epsilon$. In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to $O(1/\epsilon)$ line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR., Comment: 41 pages, updates the previous version which had a 3-approximation algorithm

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.

We study the approximability of the maximum size independent set (MIS) problem in bounded degree graphs. This is one of the most classic and widely studied NP-hard optimization problems. We focus on the well known minimum degree greedy algorithm for this problem. This algorithm iteratively chooses a minimum degree vertex in the graph, adds it to the solution and removes its neighbors, until the remaining graph is empty. The approximation ratios of this algorithm have been very widely studied, where it is augmented with an advice that tells the greedy which minimum degree vertex to choose if it is not unique. Our main contribution is a new mathematical theory for the design of such greedy algorithms with efficiently computable advice and for the analysis of their approximation ratios. With this new theory we obtain the ultimate approximation ratio of 5/4 for greedy on graphs with maximum degree 3, which completely solves the open problem from the paper by Halldorsson and Yoshihara (1995). Our algorithm is the fastest currently known algorithm with this approximation ratio on such graphs. We apply our new algorithm to the minimum vertex cover problem on graphs with maximum degree 3 to obtain a substantially faster 6/5-approximation algorithm than the one currently known. We complement our positive, upper bound results with negative, lower bound results which prove that the problem of designing good advice for greedy is computationally hard and even hard to approximate on various classes of graphs. These results significantly improve on such previously known hardness results. Moreover, these results suggest that obtaining the upper bound results on the design and analysis of greedy advice is non-trivial., Comment: Preliminary version of this paper has been published in the proceedings of ACM-SIAM SODA 2020

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges form a planar graph. By planar duality this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.

Given a set D of n unit disks in the plane and an integer k <= n, the maximum area connected subset problem asks for a set D' subseteq D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.

Given a set D of n unit disks in the plane and an integer k <= n, the maximum area connected subset problem asks for a set D' subseteq D of size k that maximizes the area of the union of disks, under the constraint that this union is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint. We prove that the problem is NP-hard and analyze a greedy algorithm, proving that it is a 1/2-approximation. We then give a polynomial-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of epsilon k disks that are not drawn from the input. Additionally, for two special cases of the problem we design a PTAS without resource augmentation.