Search

In MAXSPACE, given a set of ads A , one wants to schedule a subset A ′ ⊆ A into K slots B 1 , ⋯ , B K of size L. Each ad A i ∈ A has a size s i and a frequency w i . A schedule is feasible if the total size of ads in any slot is at most L, and each ad A i ∈ A ′ appears in exactly w i slots and at most once per slot. The goal is to find a feasible schedule that maximizes the sum of the space occupied by all slots. We consider a generalization called MAXSPACE-R for which an ad A i also has a release date r i and may only appear in a slot B j if j ≥ r i . For this variant, we give a 1/9-approximation algorithm. Furthermore, we consider MAXSPACE-RDV for which an ad A i also has a deadline d i (and may only appear in a slot B j with r i ≤ j ≤ d i ), and a value v i that is the gain of each assigned copy of A i (which can be unrelated to s i ). We present a polynomial-time approximation scheme for this problem when K is bounded by a constant. This is the best factor one can expect since MAXSPACE is strongly NP-hard, even if K = 2 . [ABSTRACT FROM AUTHOR]

In 2015, Haviv introduced the Remote set problem (RSP) and studied the complexity of the covering radius problem (CRP), which is a classical problem in lattices. The RSP aims to identify a set containing a point that is sufficiently distant from a given lattice L . It introduced a new method for analyzing the complexity of CRP. An open question in RSP is whether we can obtain the approximation factor γ = 1 / 2 . This paper investigates this question and proposes a probabilistic polynomial-time algorithm for RSP with an approximation factor of 1 / 2 - 1 / (c λ n (p)) , where c ∈ Z + and λ n (p) is the n-th successive minima in lattice under l p -norm. For a given lattice L with rank n and positive integer d, our algorithm outputs a set S of size d in polynomial time. This set S includes a point at least (1 2 - 1 c λ n (p) ) ρ (p) (L) from lattice L with a probability greater than 1 - 1 / 2 d . Here, c is a positive integer and ρ (p) (L) denotes the covering radius of L in l p -norm( 1 ≤ p ≤ ∞ ). Based on this, we obtain that GAPCRP 2 + 1 / 2 O (n) belongs to the complexity class coRP, and we provide new reductions from GAPCRP to GAPCVP. [ABSTRACT FROM AUTHOR]

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Notice that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in O (log n) time. Therefore, upper-bounding the numbers used as vertex labels also upper-bounds the space complexity of storing the graph in the database. We show that every n-vertex, m-edge, d-degenerate graph can be made a sum graph by adding at most m isolated vertices to it, such that the largest numbers used as vertex labels grows as O (n 2 d) . This enables us to store the graph using O (m log n) bits of memory. For sparse graphs (graphs with O (n) edges), this matches the trivial lower bound of Ω (n log n) . As planar graphs and forests have constant degeneracy, our result implies an upper bound of O (n 2) on their label numbers. The previously best known upper bound on the numbers needed for labelling general graphs with the minimum number of isolated vertices was O (4 n) , due to Kratochvíl, Miller & Nguyen (2001). Furthermore, their proof was existential, whereas our labelling can be constructed in polynomial time. [ABSTRACT FROM AUTHOR]

The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem (Bar-Noy et al. STOC 2001) and also a QPTAS (Höhn et al. ICALP 2018). In this paper we study fixed-parameter algorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of f (k) ⋅ n O 휖 (1) that outputs a solution with at most (1 + 휖)k tasks or asserts that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times. We show that the other two algorithms extend also to the weighted case of the problem, at the expense of losing a factor of 1 + 휖 in the cost of the selected tasks. [ABSTRACT FROM AUTHOR]

A classical result by Myerson (Math. Oper. Res. 6(1), 58-73, 1981) gives a characterization of an optimal auction for any given distribution of valuations of the bidders. We consider the situation where the distribution is not explicitly given but can be observed in a sample of auction results from the same distribution. A seminal paper by Morgenstern and Roughgarden (Adv.Neural Inf. Process. Syst. 28, 2015) proposes to learn a near-optimal auction from the hypothesis class of t-level auctions. They prove a bound on the sample complexity, i.e., the function f(ε,δ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$f(\varepsilon , \delta )$$\end{document} of required samples to guarantee a certain level of precision (1-ε)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(1-\varepsilon )$$\end{document} with a probability of at least (1-δ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(1-\delta )$$\end{document}, for the general single-parameter case and a tighter bound for the very restricted matroid case. We show a new bound for the case of independence systems, that widely generalizes matroids and contains several important combinatorial optimization problems. This bound of O~H2n4ε3\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\tilde{O}\left( \nicefrac {H^2n^4}{\varepsilon ^3}\right) $$\end{document} falls neatly between those known for the general and the matroid case. The class of independence systems contains several well known NP-hard problems such as knapsack. Therefore, the allocation itself might in practice be limited to α\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\alpha $$\end{document}-approximate solutions. In a second result we show that an approximation algorithm can be used without compromising the sample complexity. Also, the precision is affected only mildly, resulting in a factor of α·(1-ε)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\alpha \cdot (1-\varepsilon )$$\end{document}. [ABSTRACT FROM AUTHOR]

Impartial selection has recently received much attention within the multi-agent systems community. The task is, given a directed graph representing nominations to the members of a community by other members, to select a member with the highest number of nominations. This seemingly trivial goal becomes challenging when there is an additional impartiality constraint, requiring that no single member can influence her chance of being selected. Recent progress has identified impartial selection rules with optimal approximation ratios. Moreover, it was noted that worst-case instances are graphs with few vertices. Motivated by this fact, we propose the study of additive approximation, the difference between the highest number of nominations and the number of nominations of the selected member, as an alternative measure of the quality of impartial selection. Our positive results include two randomized impartial selection mechanisms which have additive approximation guarantees of Θ (n) and Θ (n 2 / 3 ln 1 / 3 n) for the two most studied models in the literature, where n denotes the community size. We complement our positive results by providing negative results for various cases. First, we provide a characterization for the interesting class of strong sample mechanisms, which allows us to obtain lower bounds of n − 2, and of Ω (n) for their deterministic and randomized variants respectively. Finally, we present a general lower bound of 3 for all deterministic impartial mechanisms. [ABSTRACT FROM AUTHOR]

We study the problem of finding maximum weakly stable matchings when preference lists are incomplete and contain one-sided ties of bounded length. We show that if the tie length is at most L, then it is possible to achieve an approximation ratio of 1 + (1 − 1 L) L . We also show that the same ratio is an upper bound on the integrality gap, which matches the known lower bound. In the case where the tie length is at most 2, our result implies an approximation ratio and integrality gap of 5 4 , which matches the known UG-hardness result. [ABSTRACT FROM AUTHOR]

We determine the power of the weighted sum scalarization with respect to the computation of approximations for general multiobjective minimization and maximization problems. Additionally, we introduce a new multi-factor notion of approximation that is specifically tailored to the multiobjective case and its inherent trade-offs between different objectives. For minimization problems, we provide an efficient algorithm that computes an approximation of a multiobjective problem by using an exact or approximate algorithm for its weighted sum scalarization. In case that an exact algorithm for the weighted sum scalarization is used, this algorithm comes arbitrarily close to the best approximation quality that is obtainable by supported solutions – both with respect to the common notion of approximation and with respect to the new multi-factor notion. Moreover, the algorithm yields the currently best approximation results for several well-known multiobjective minimization problems. For maximization problems, however, we show that a polynomial approximation guarantee can, in general, not be obtained in more than one of the objective functions simultaneously by supported solutions. [ABSTRACT FROM AUTHOR]

We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking O(ε− 1) passes: (1) a (1 − e− 1 − ε)-approximation algorithm for the cardinality-constrained problem, (2) a (0.5 − ε)-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run deterministically in O∗(n) time, using O∗(K) space, where n is the size of the ground set and K is the size of the knapsack. Here the term O∗ hides a polynomial of log K and ε− 1. Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes O (n ε − 1 log (ε − 1 log K)) time, improving on the algorithm of Badanidiyuru and Vondrák that takes O (n ε − 1 log (ε − 1 K)) time. [ABSTRACT FROM AUTHOR]

In the k-Connectivity Augmentation Problem we are given a k-edge-connected graph and a set of additional edges called links. Our goal is to find a set of links of minimum size whose addition to the graph makes it (k + 1)-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case k = 1 (a.k.a. the Tree Augmentation Problem or TAP) or k = 2 (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-2 approximation algorithms are known for TAP, for CacAP only recently this barrier was breached (hence for k-Connectivity Augmentation in general). As a first step towards better approximation algorithms for CacAP, we consider the special case where the input cactus consists of a single cycle, the Cycle Augmentation Problem (CycAP). This apparently simple special case retains part of the hardness of the general case. In particular, we are able to show that it is APX-hard. In this paper we present a combinatorial 3 2 + ε -approximation for CycAP, for any constant ε > 0. We also present an LP formulation with a matching integrality gap: this might be useful to address the general case of the problem. [ABSTRACT FROM AUTHOR]

We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to Bertsimas et al. (Math. Program. 98(1-3), 49–71 2003), once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs' processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of 2 − 𝜖 for the case of unrelated machines. [ABSTRACT FROM AUTHOR]

We consider approximability of two optimization problems called Minimum Open k-Monopoly (Min-Open-k-Monopoly) and Minimum Partial Open k-Monopoly (Min-P-Open-k-Monopoly), where k is a fixed positive integer. The objective, in Min-Open-k-Monopoly, is to find a minimum cardinality vertex set S ⊆ V in a given graph G = (V,E) such that | N (v) ∩ S | ≥ 1 2 | N (v) | + k , for every vertex v ∈ V. On the other hand, given a graph G = (V,E), in Min-P-Open-k-Monopoly it is required to find a minimum cardinality vertex set S ⊆ V such that | N (v) ∩ S | ≥ 1 2 | N (v) | + k , for every v ∈ V ∖ S. We prove that Min-Open-k-Monopoly and Min-P-Open-k-Monopoly are approximable within a factor of O (log n) . Then, we show that these two problems cannot be approximated within a factor of (1 3 − 𝜖) ln n and (1 4 − 𝜖) ln n , respectively, for any 𝜖 > 0, unless N P ⊆ D t i m e (n O (log log n)). For 4-regular graphs, we prove that these two problems are APX-complete. Min-Open-1-Monopoly can be approximated within a factor of 26 21 ≈ 1.2381 where as Min-P-Open-1-Monopoly can be approximated within a factor of 1.65153. For k ≥ 2, we also present approximation algorithms for these two problems for (2k + 2)-regular graphs. [ABSTRACT FROM AUTHOR]

We consider non-preemptive scheduling of MapReduce jobs consisting of multiple map-reduce rounds so as to minimize their average weighted completion time on identical or unrelated processor environments. For identical processors, we present LP-based O(1)-approximation algorithms, while for unrelated processors the approximation ratio naturally depends on the maximum number of rounds of any job (which is a small constant in practice). For the single-round case, we substantially improve on previously best known approximation ratios, while also we introduce into our model the crucial cost of the data shuffle phase, i.e., the cost for the transmission of intermediate data from Map to Reduce tasks. Finally, we evaluate our algorithms via simulations in the general case of unrelated processors, comparing them with a lower bound on the optimal cost of the problem as well as with a fast algorithm which combines a simple online assignment of tasks to processors with a standard scheduling policy. As we observe, for random instances that capture data locality issues, our algorithm achieves an excellent average performance. [ABSTRACT FROM AUTHOR]

We study the problem of computing a longest increasing subsequence in a sequence S of n distinct elements in the presence of persistent comparison errors. In this model, Braverman and Mossel (Noisy sorting without resampling, SODA 2008, pages 268–276, 2008) every comparison between two elements can return the wrong result with some fixed (small) probability p, and comparisons cannot be repeated. Computing the longest increasing subsequence exactly is impossible in this model, therefore, the objective is to identify a subsequence that (i) is indeed increasing and (ii) has a length that approximates the length of the longest increasing subsequence. We present asymptotically tight upper and lower bounds on both the approximation factor and the running time. In particular, we present an algorithm that computes an O (log n) -approximation in O (n log n) time, with high probability. This approximation relies on the fact that we can approximately sort (Geissmann et al. Optimal Sorting with Persistent Comparison Errors, ArXiv e-prints 1804.07575, 2018) n elements in O (n log n) time such that the maximum dislocation of an element is O (log n) . For the lower bounds, we prove that (i) there is a set of sequences, such that on a sequence picked randomly from this set every algorithm must return an Ω (log n) -approximation with high probability, and (ii) any log n -approximation algorithm for longest increasing subsequence requires Ω (n log n) comparisons, even in the absence of errors. [ABSTRACT FROM AUTHOR]

We study the problem of finding a minimum weight connected subgraph spanning at least k vertices on planar, node-weighted graphs. We give a (4 + ε)-approximation algorithm for this problem. We achieve this by utilizing the recent Lagrangian-multiplier preserving (LMP) primal-dual 3-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al. (SWAT'16) and adopting an approach by Chudak et al. (Math. Prog. '04) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. '06). More generally, our approach readily gives a (4/3 ⋅ r + ε)-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an r-approximation. We argue that this can be interpreted as a generalization of an analogous result by Könemann et al. (Algorithmica '11) for partial cover problems. Together with a lower bound construction by Mestre (STACS'08) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a non-black-box fashion could not beat the factor 4/3 ⋅ r when the tree merging step relies only on the solutions output by the LMP algorithm. [ABSTRACT FROM AUTHOR]

Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require Õ (τ / π (v)) operations to approximate the probability π(v) of a state v in a chain with mixing time τ, and even the best available techniques still have complexity Õ (τ 1.5 / π (v) 0.5) ; and since these complexities depend inversely on π(v), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-π(v) barrier". [ABSTRACT FROM AUTHOR]

All-optical networks have been largely investigated due to their high data transmission rates. The key to the high speeds in all-optical networks is to maintain the signal in optical form, to avoid the overhead of conversion to and from electrical form at the intermediate nodes. In the traditional WDM technology the spectrum of light that can be transmitted through the optical fiber has been divided into frequency intervals of fixed width with a gap of unused frequencies between them. In this context the term wavelength refers to each of these predefined frequency intervals. An alternative architecture emerging in very recent studies is to move towards a flexible model in which the usable frequency intervals are of variable width. Every lightpath is assigned a frequency interval which remains fixed through all the links it traverses. Two different lightpaths using the same link have to be assigned disjoint sub-spectra. This technology is termed flex-grid or flex-spectrum. The introduction of this technology requires the generalization of many optimization problems that have been studied for the fixed-grid technology. Moreover it implies new problems that are irrelevant or trivial in the current technology. In this work we focus on bandwidth utilization in path toplogy and consider two wavelength assignment, or in graph theoretic terms coloring, problems where the goal is to maximize the total profit. We obtain bandwidth maximization as a special case. [ABSTRACT FROM AUTHOR]

We investigate a variant of the so-called Internet Shopping problem introduced by Blazewicz et al. (Appl. Math. Comput. Sci. 20, 385–390, 2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a certain threshold. Although the problem is NP-hard, we provide exact algorithms for several cases, e.g. when each shop sells only two items, and an FPT algorithm for the number of items, or for the number of shops when all prices are equal. We complement each result with hardness proofs in order to draw a tight boundary between tractable and intractable cases. Finally, we give an approximation algorithm and hardness results for the problem of maximising the sum of discounts [ABSTRACT FROM AUTHOR]

We study Parallel Task Scheduling Pm|sizej|Cmax with a constant number of machines. This problem is known to be strongly NP-complete for each m ≥ 5, while it is solvable in pseudo-polynomial time for each m ≤ 3. We give a positive answer to the long-standing open question whether this problem is strongly NP-complete for m = 4. As a second result, we improve the lower bound of 12 11 for approximating pseudo-polynomial Strip Packing to 5 4 . Since the best known approximation algorithm for this problem has a ratio of 5 4 + ε , this result almost closes the gap between approximation ratio and inapproximability result. Both results are proved by a reduction from the strongly NP-complete problem 3-Partition. [ABSTRACT FROM AUTHOR]

We present a series of results regarding conceptually simple algorithms for bipartite matching in various online and related models. We first consider a deterministic adversarial model. The best approximation ratio in this model is 1/2, which is achieved by any greedy algorithm. Dürr et al. (2016) presented a 2-pass algorithm Category-Advice with approximation ratio 3/5. We extend their algorithm to multiple passes. We prove the exact approximation ratio for the k-pass Category-Advice algorithm for all k ≥ 1, and show that the approximation ratio converges quickly to the inverse of the golden ratio 2 / (1 + 5) ≈ 0.618 as k goes to infinity. We then consider a natural adaptation of a well-known offline MinGreedy algorithm to the online stochastic IID model, which we call MinDegree. In spite of excellent empirical performance of MinGreedy, it was recently shown to have approximation ratio 1/2 in the adversarial offline setting — the approximation ratio achieved by any greedy algorithm. Our result in the online known IID model is, in spirit, similar to the offline result, but the proof is different. We show that MinDegree cannot achieve an approximation ratio better than 1 − 1/e, which is guaranteed by any consistent greedy algorithm in the known IID model. Finally, following the work in Besser and Poloczek (Algorithmica 2017(1), 201–234, 2017), we depart from an adversarial or stochastic ordering and investigate a natural randomized algorithm (MinRanking) in the priority model. Although the priority model allows the algorithm to choose the input ordering in a general but well defined way, this natural algorithm cannot obtain the approximation of the Ranking algorithm in the ROM model. [ABSTRACT FROM AUTHOR]

We study ordinal approximation algorithms for maximum-weight bipartite matchings. Such algorithms only know the ordinal preferences of the agents/nodes in the graph for their preferred matches, but must compete with fully omniscient algorithms which know the true numerical edge weights (utilities). Ordinal approximation is all about being able to produce good results with only limited information. Because of this, one important question is how much better the algorithms can be as the amount of information increases. To address this question for forming high-utility matchings between agents in X and Y , we consider three ordinal information types: when we know the preference order of only nodes in X for nodes in Y , when we know the preferences of both X and Y , and when we know the total order of the edge weights in the entire graph, although not the weights themselves. We also consider settings where only the top preferences of the agents are known to us, instead of their full preference orderings. We design new ordinal approximation algorithms for each of these settings, and quantify how well such algorithms perform as the amount of information given to them increases. [ABSTRACT FROM AUTHOR]

In this paper we study the online variant of two well-known Steiner tree problems. In the online setting, the input consists of a sequence of terminals; upon arrival of a terminal, the online algorithm must irrevocably buy a subset of edges and vertices of the graph so as to guarantee the connectivity of the currently revealed part of the input. More precisely, we first study the online node-weighted Steiner tree problem, in which both edges and vertices are weighted, and the objective is to minimize the total cost of edges and vertices in the solution. We then address the online priority Steiner tree problem, in which each edge and each request are associated with a priority value, which corresponds to their bandwidth support and requirement, respectively. Both problems have applications in the domain of multicast network communications and have been studied from the point of view of approximation algorithms. Motivated by the observation that competitive analysis gives very pessimistic and unsatisfactory results when the only relevant parameter is the number of terminals, we introduce an approach based on parameterized analysis of online algorithms. In particular, we base the analysis on additional parameters that help reveal the true complexity of the underlying problem, and allow a much finer classification of online algorithms based on their performance. More specifically, for the online node-weighted Steiner tree problem, we show a tight bound of Θ(max{min{α,k},log k}) on the competitive ratio, where α is the ratio of the maximum node weight to the minimum node weight and k is the number of terminals. For the online priority Steiner tree problem, we show corresponding tight bounds of Θ (b log k b) , when k > b and Θ(k), when k ≤ b, where b is the number of priority levels and k is the number of terminals. Our main results apply to both deterministic and randomized algorithms, as well as to generalized versions of the problems (i.e., to Steiner forest variants). [ABSTRACT FROM AUTHOR]

We study the complexity of motivating time-inconsistent agents to complete long term projects in a graph-based planning model proposed by Kleinberg and Oren (2014). Given a task graph G with n nodes, our objective is to guide an agent towards a target node t under certain budget constraints. The crux is that the agent may change its strategy over time due to its present-bias. We consider two strategies to guide the agent. First, a single reward is placed at t and arbitrary edges can be removed from G. Secondly, rewards can be placed at arbitrary nodes of G but no edges must be deleted. In both cases we show that it is NP-complete to decide if a given budget is sufficient to keep the agent motivated. For the first setting, we give complementing upper and lower bounds on the approximability of the minimum required budget. In particular, we devise a (1 + n) -approximation algorithm and prove NP-hardness for ratios greater than n / 3 . We also argue that the second setting does not permit any efficient approximation unless P = NP. [ABSTRACT FROM AUTHOR]

We study the design of cost-sharing protocols for two fundamental resource allocation problems, the Set Cover and the Steiner Tree Problem, under environments of incomplete information (Bayesian model). Our objective is to design protocols where the worst-case Bayesian Nash equilibria have low cost, i.e. the Bayesian Price of Anarchy (PoA) is minimized. Although budget balance is a very natural requirement, it puts considerable restrictions on the design space, resulting in high PoA. We propose an alternative, relaxed requirement called budget balance in the equilibrium (BBiE). We show an interesting connection between algorithms for Oblivious Stochastic optimization problems and cost-sharing design with low PoA. We exploit this connection for both problems and we enforce approximate solutions of the stochastic problem, as Bayesian Nash equilibria, with the same guarantees on the PoA. More interestingly, we show how to obtain the same bounds on the PoA, by using anonymous posted prices which are desirable because they are easy to implement and, as we show, induce dominant strategies for the players. [ABSTRACT FROM AUTHOR]

We investigate the problem of equilibrium computation for "large" n-player games. Large games have a Lipschitz-type property that no single player's utility is greatly affected by any other individual player's actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players' payoffs to change by at most 1n. We study algorithms having query access to the game's payoff function, aiming to find ε-Nash equilibria. We seek algorithms that obtain ε as small as possible, in time polynomial in n. Our main result is a randomised algorithm that achieves ε approaching 18 for 2-strategy games in a completely uncoupled setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players' payoffs/actions. O(log n) rounds/queries are required. We also show how to obtain a slight improvement over 18, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters. [ABSTRACT FROM AUTHOR]

We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (SRI) that are degree constrained, i.e., preference lists are of bounded length. The first variant, EGALD-SRI, involves finding an egalitarian stable matching in solvable instances of SRI with preference lists of length at most d. We show that this problem is NP-hard even if d = 3. On the positive side we give a 2d+37-approximation algorithm for d ∈{3,4,5} which improves on the known bound of 2 for the unbounded preference list case. In the second variant of SRI, called d-SRTI, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-SRTI admits a stable matching is NP-complete even if d = 3. We also consider the "most stable" version of this problem and prove a strong inapproximability bound for the d = 3 case. However for d = 2 we show that the latter problem can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of set cover problems that satisfy a special property which we call the small neighborhood cover property. This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified sequential, parallel and distributed algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. The algorithms run in NC in the parallel setting and can be executed in polylogarithmic communication rounds in the distributed setting. [ABSTRACT FROM AUTHOR]

The edge dominating set problem (EDS) is to compute a minimum size edge set such that every edge is dominated by some edge in it. This paper considers a variant of EDS with extensions of multiple and connected dominations combined. In the b-EDS problem, each edge needs to be dominated b times. Connected EDS requires an edge dominating set to be connected while it has to form a tree in Tree Cover. Although each of EDS, b-EDS, and Connected EDS (or Tree Cover) has been well studied, each known to be approximable within 2 (or 8/3 for b-EDS in general), nothing is known when these extensions are imposed simultaneously on EDS unlike in the case of the (vertex) dominating set problem. We consider Connected 2-EDS and 2-Tree Cover (i.e., a combination of 2-EDS and Tree Cover), and present a polynomial algorithm approximating each within 2. Moreover, it will be shown that the single tree computed is no larger than twice the optimum for (not necessarily connected) 2-EDS, thus also approximating 2-EDS equally well. It also implies that 2-EDS with clustering properties can be approximated within 2 as well. [ABSTRACT FROM AUTHOR]

We present a fast combinatorial 3/4-approximation algorithm for the maximum asymmetric TSP with weights zero and one. The approximation factor of this algorithm matches the currently best one given by Bläser in 2004 and based on linear programming. Our algorithm first computes a maximum size matching and a maximum weight cycle cover without certain cycles of length two but possibly with half-edges - a half-edge of a given edge e is informally speaking a half of e that contains one of the endpoints of e. Then from the computed matching and cycle cover it extracts a set of paths, whose weight is large enough to be able to construct a traveling salesman tour with the claimed guarantee. [ABSTRACT FROM AUTHOR]

Local computation algorithms (LCAs) produce small parts of a single (possibly approximate) solution to a given search problem using time and space sublinear in the size of the input. In this work we present LCAs whose time complexity (and usually also space complexity) is independent of the input size. Specifically, we give (1) a (1 - ϵ)-approximation LCA to the maximum weight acyclic edge set, (2) LCAs for approximating multicut and integer multicommodity flow on trees, and (3) a local reduction of weighted matching to any unweighted matching LCA, such that the running time of the weighted matching LCA is d times (where d is the maximal degree) the running time of the unweighted matching LCA, (and therefore independent of the edge weight function). [ABSTRACT FROM AUTHOR]

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all d≥2.⌈k/2⌉. For the case of k-vertex-connectedness, we achieve constant approximation ratios for d≥2k-1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2.⌈k/2⌉ (for k-edge-connectivity) or 2k-1 (for k-vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is A P X-hard. [ABSTRACT FROM AUTHOR]

We study several natural instances of the geometric hitting set problem for input consisting of sets of line segments (and rays, lines) having a small number of distinct slopes. These problems model path monitoring (e.g., on road networks) using the fewest sensors (the "hitting points"). We give approximation algorithms for cases including (i) lines of 3 slopes in the plane, (ii) vertical lines and horizontal segments, (iii) pairs of horizontal/vertical segments. We give hardness and hardness of approximation results for these problems. We prove that the hitting set problem for vertical lines and horizontal rays is polynomially solvable. [ABSTRACT FROM AUTHOR]

Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1−1/ e). (2) On the positive side we present (i) an $O(\sqrt n)$ -approximation algorithm for general concave externality functions, (ii) an O(log m)-approximation algorithm for linear externality functions, and (iii) a $\frac {5}{18}(1-1/e)$ -approximation algorithm for 2-hop step function externalities. We also improve the result from [7] for 1-hop step function externalities by giving a $\frac {1}{2}(1-1/e)$ -approximation algorithm. [ABSTRACT FROM AUTHOR]

R. Lavi and C. Swamy (FOCS 2005, J. ACM 58(6), 25, 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees. [ABSTRACT FROM AUTHOR]

We study two natural extensions of Constraint Satisfaction Problems (CSPs). Balance-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of Hard-Max-CSP consists of soft constraints and hard constraints, and the goal is to maximize the weight of satisfied soft constraints while satisfying all the hard constraints. These two extensions contain many fundamental problems not captured by CSPs, and challenge traditional theories about CSPs in a more general framework. Max-2-SAT and Max-Horn-SAT are the only two nontrivial classes of Boolean CSPs that admit a robust satisfibiality algorithm, i.e., an algorithm that finds an assignment satisfying at least (1 − g( ε)) fraction of constraints given a (1 − ε)-satisfiable instance, where g( ε) → 0 as ε → 0, and g(0) = 0. We prove the inapproximability of these problems with balance or hard constraints, showing that each variant changes the nature of the problems significantly (in different ways). For instance, deciding whether an instance of 2-SAT admits a balanced assignment is NP-hard, and for Max-2-SAT with hard constraints, it is hard to find a constant-factor approximation even on (1 − ε)-satisfiable instances (in particular, the version with hard constraints does not admit a robust satisfiability algorithm). We also study hardness results for a certain CSP over a larger domain capturing ordering constraints: we show that hard constraints rule out constant-factor approximation algorithms. All our hardness results are almost optimal - they completely rule out algorithms with certain properties, or can be matched by simple extensions to existing algorithms. [ABSTRACT FROM AUTHOR]

Given a graph G with a set of terminals, two weight functions c and d defined on the edge set of G, and a bound D, a popular NP-hard problem in designing networks is to find the minimum cost Steiner tree (under function c) in G, to connect all terminals in such a way that its diameter (under function d) is bounded by D. Marathe et al. (J. Algoritm. 28(1), 142-171, ) proposed an ( O(ln n), O(ln n)) approximation algorithm for this bicriteria problem, where n is the number of terminals. The first factor reflects the approximation ratio on the diameter bound D, and the second factor indicates the cost-approximation ratio. Later, Kapoor and Sarwat (Theory Comput. Syst. 41(4), 779-794, ) introduced a parameterized approximation algorithm with performance guarantee of $(O(p \cdot \frac {\ln n}{\ln p}), O(\frac {\ln n}{\ln p}))$ for any input value p>1, by which one can improve the approximation factor for cost at the price of worsening the approximation factor of diameter. In this paper, we consider the reverse scenario in which minimizing the diameter of the solution is more important. We first propose a parameterized approximation algorithm with performance guarantee of $(O(\frac {\ln n}{\ln p}),O(p \cdot H_{p} \cdot \frac {\ln n}{\ln p}))$, where H = 1+1/2+...+1/ p is the p harmonic number. Parameter p is part of the input and this algorithm runs in polynomial time for constant values of p. We also present another algorithm with approximation ratio of $(O(\frac {\ln n}{\ln p}),O(\mu \cdot p \cdot \frac {\ln n}{\ln p}))$ which relies on the approximation factor ( μ) of the NP-hard problem min-degree constrained minimum spanning tree. [ABSTRACT FROM AUTHOR]

Given a simple undirected graph G = ( V, E) and an integer k < | V|, the Sparsest k- Subgraph problem asks for a set of k vertices which induces the minimum number of edges. As a generalization of the classical independent set problem, Sparsest k- Subgraph is 퓝퓟-hard and even not approximable unless 퓟퓝퓟 in general graphs. Thus, we investigate Sparsest k- Subgraph in graph classes where independent set is polynomial-time solvable, such as subclasses of perfect graphs. Our two main results are the 퓝퓟-hardness of Sparsest k- Subgraph on chordal graphs, and a greedy 2-approximation algorithm. Finally, we also show how to derive a P T A S for Sparsest k- Subgraph on proper interval graphs. [ABSTRACT FROM AUTHOR]

An orientation of an undirected graph G is a directed graph obtained by replacing each edge { u, v} of G by exactly one of the arcs ( u, v) or ( v, u). In the min-sum k -paths orientation problem, the input is an undirected graph G and ordered pairs ( s, t), where i∈{1,2,..., k}. The goal is to find an orientation of G that minimizes the sum over all i∈{1,2,..., k} of the distance from s to t. In the min-sum k edge-disjoint paths problem, the input is the same, however the goal is to find for every i∈{1,2,..., k} a path between s and t so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed k≥2, the question of N P-hardness for the min-sum k-paths orientation problem and for the min-sum k edge-disjoint paths problem has been open for more than two decades. We study the complexity of these problems when k=2. We exhibit a PTAS for the min-sum 2-paths orientation problem. A by-product of this PTAS is a reduction from the min-sum 2-paths orientation problem to the min-sum 2 edge-disjoint paths problem. The implications of this reduction are: (i) an NP-hardness proof for the min-sum 2-paths orientation problem yields an NP-hardness proof for the min-sum 2 edge-disjoint paths problem, and (ii) any approximation algorithm for the min-sum 2 edge-disjoint paths problem can be used to construct an approximation algorithm for the min-sum 2-paths orientation problem with the same approximation guarantee and only an additive polynomial increase in the running time. [ABSTRACT FROM AUTHOR]

In the Fixed Cost k-Flow problem, we are given a graph G = ( V, E) with edge-capacities { u∣ e ∈ E} and edge-costs { c∣ e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = ( A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ⊆ A ∪ B of minimum size | S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an $O(\sqrt {k\log k})$ approximation for this problem. We also show that we can compute a solution of optimum size with Ω( k/polylog( n)) paths, where n = | A| + | B|. In the Generalized-P2P problem we are given an undirected graph G = ( V, E) with edge-costs and integer charges { b : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design []. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log n approximation scheme for it using Group Steiner Tree techniques. [ABSTRACT FROM AUTHOR]

Given a directed acyclic graph with non-negative edge-weights, two vertices s and t, and a threshold-weight L, we present a fully-polynomial time approximation-scheme for the problem of counting the s- t paths of length at most L. This is best possible, as we also show that the problem is #P-complete. We then show that, unless P=NP, there is no finite approximation to the bi-criteria version of the problem: count the number of s- t paths of length at most L in the first criterion, and of length at most L in the second criterion. On the positive side, we extend the approximation scheme for the relaxed version of the problem, where, given thresholds L and L, we relax the requirement of the s- t paths to have length exactly at most L, and allow the paths to have length at most L : = (1+ δ) L, for any δ > 0. [ABSTRACT FROM AUTHOR]

We study the k-level uncapacitated facility location problem ( k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most α times OPT, where α is an increasing function of k, with $\lim _{k\to \infty } \alpha _{k} = 3$. Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA'98) originally used for the group Steiner tree problem. We improve the approximation ratio for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5. Second, we give a simple interpretation of the randomization process (Li ICALP'2011) for 1-level UFL in terms of solving an auxiliary (factor revealing) LP. Armed with this simple view point, we exercise the randomization on our algorithm for the k-level UFL. We further improve the approximation ratio for all k ≥ 3, obtaining 1.97, 2.09, and 2.19 for k = 3,4, and 5. Third, we extend our algorithm to the k-level UFL with penalties ( k-level UFLWP), in which the setting is the same as k-level UFL except that the planner has the option to pay a penalty instead of connecting chosen clients. [ABSTRACT FROM AUTHOR]

We study the problem of designing truthful mechanisms for makespan minimization in scheduling. In particular, we consider randomized mechanisms for a restriction of the general multi-dimensional domain (i.e., unrelated machines). In a sense, our setting is the simplest multi-dimensional setting, where each machine holds privately only a single-bit of information. Some of the impossibility results for deterministic mechanisms carry over our setting as well. We prove a separation between truthful-in-expectation and universally truthful mechanisms for makespan minimization: We first show how to design an optimal truthful-in-expectation mechanism, and then prove lower bounds on the approximation guarantee of universally truthful mechanisms. [ABSTRACT FROM AUTHOR]

This article belongs to the Topical Collection: Special Issue on Approximation and Online Algorithms (2019) Guest Editors: Evripidis Bampis and Nicole Megow The Special Issue I Approximation and Online Algorithms i focuses on the design and analysis of algorithms for online and computationally hard problems. Online algorithms deal with problems where the information arrives over time, or more generally, when the algorithm operates under some state of uncertainty. Cormode and Vesely consider in their contribution I Streaming Algorithms for Bin Packing and Vector Scheduling i problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling. [Extracted from the article]

An edge dominating set in a graph G = ( V, E) is a subset S of edges such that each edge in E − S is adjacent to at least one edge in S. The edge dominating set problem, to find an edge dominating set of minimum size, is a basic and important NP-hard problem that has been extensively studied in approximation algorithms and parameterized complexity. In this paper, we present improved hardness results and parameterized approximation algorithms for edge dominating set. More precisely, we first show that it is NP-hard to approximate edge dominatingset in polynomial time within a factor better than 1.18. Next, we give a parameterized approximation schema (with respect to the standard parameter) for the problem and, finally, we develop an O(1.821)-time exact algorithm where τ is the size of a minimum vertex cover of G. [ABSTRACT FROM AUTHOR]

Motivated by issues in allocating limited preventative resources to protect a landscape against the spread of a wildfire from a stochastic ignition point, we give approximation algorithms for a new family of stochastic optimization problems. We study several models in which we are given a graph with edge costs and node values, a budget, and a probabilistic distribution over ignition nodes: the goal is to find a budget-limited set of edges whose removal protects the largest expected value from being reachable from a stochastic ignition node. In particular, 2-stage stochastic models capture the tradeoffs between preventative treatment and real-time response. The resulting stochastic cut problems are interesting in their own right, and capture a number of related interdiction problems, both in the domain of computational sustainability, and beyond. In trees, even the deterministic problem is (weakly) NP hard: we give a Polynomial-time approximation scheme for the single-stage stochastic case in trees when the number of scenarios is constant. For the 2-stage stochastic model in trees we give a $(1-\frac {1}{e})<(1-(1-1/2\delta )^{2\delta })$-approximation in trees which violates the budget by a factor of at most 2 (δ is the tree diameter), and a 0.387-approximation that is budget-balanced. For the single-stage stochastic case in trees we can save (1− (1 − 1/ δ) OPT without violating the budget. Single-stage results extend to general graphs with an additional O(log n) loss in budget-balancedness. Multistage results have a similar extension when the number of scenarios is constant. In an extension of the single-stage model where both ignition and spread are stochastic we give a $(1-\frac {1}{e})$-approximation in trees. Our approximation guarantees in trees also hold for multistage and probabilistic-element-failure generalizations of the Maximum Coverage with Knapsack Constraint problem (MCKP). [ABSTRACT FROM AUTHOR]

The Travelling Salesman Problem is one of the fundamental and intensively studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with an approximation factor of $\frac{3}{2}$, even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only $\frac{4}{3}$. Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis Gharan et al. (FOCS, 550-559, ), and then by Mömke and Svensson (FOCS, 560-569, ). In this paper, we provide an improved analysis of the approach presented in Mömke and Svensson (FOCS, 560-569, ) yielding a bound of $\frac{13}{9}$ on the approximation factor, as well as a bound of $\frac{19}{12}+\varepsilon$ for any ε>0 for a more general Travelling Salesman Path Problem in graphic metrics. [ABSTRACT FROM AUTHOR]

This paper introduces the kissing problem: given a rectangular room with n people in it, what is the most efficient way for each pair of people to kiss each other goodbye? The room is viewed as a set of pixels that form a subset of the integer grid. At most one person can stand on a pixel at once, and people move horizontally or vertically. In order to move into a pixel in time step t, the pixel must be empty in time step t−1. The paper gives one algorithm for kissing everyone goodbye. This paper gives optimal solutions for small cases, which were found using a heuristic state space search (IDA*). [ABSTRACT FROM AUTHOR]

We introduce a novel pricing and resource allocation approach for batch jobs on cloud systems. In our economic model, users submit jobs with a value function that specifies willingness to pay as a function of job due dates. The cloud provider in response allocates a subset of these jobs, taking into advantage the flexibility of allocating resources to jobs in the cloud environment. Focusing on social-welfare as the system objective (especially relevant for private or in-house clouds), we construct a resource allocation algorithm which provides a small approximation factor that approaches 2 as the number of servers increases. An appealing property of our scheme is that jobs are allocated non-preemptively, i.e., jobs run in one shot without interruption. This property has practical significance, as it avoids significant network and storage resources for checkpointing. Based on this algorithm, we then design an efficient truthful-in-expectation mechanism, which significantly improves the running complexity of black-box reduction mechanisms that can be applied to the problem, thereby facilitating its implementation in real systems. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of scheduling jobs on multiple speed-scaled processors, i.e., we have constant α>1 such that running a processor at speed s results in energy consumption s per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines, flow time, and weighted flow time. For any type of delay cost functions, we obtain the following results: Any β-approximation algorithm for a single processor yields a randomized βB-approximation algorithm for multiple processors, where B is the αth Bell number, that is, the number of partitions of a set of size α. The generated schedule is without migration, but we compare it to an optimal schedule with migration. Hence, this result holds for migratory and non-migratory schedules. Analogously, we show that any β-competitive online algorithm for a single processor yields a βB-competitive online algorithm for multiple processors. Finally, we show that any β-approximation algorithm for multiple processors with migration yields a deterministic βB-approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes. [ABSTRACT FROM AUTHOR]