Recently, the first online complexity class,AOC, was introduced. The class consists of many online problems where each request must be either accepted or rejected, and the aim is to either minimize or maximize the number of accepted requests, while maintaining a feasible solution. AllAOC-complete problems (including Independent Set, Vertex Cover, Dominating Set, and Set Cover) have essentially the same advice complexity. In this paper, we study weighted versions of problems inAOC, i.e., each request comes with a weight and the aim is to either minimize or maximize the total weight of the accepted requests. In contrast to the unweighted versions, we show that there is a significant difference in the advice complexity of complete minimization and maximization problems. We also show that our algorithmic techniques for dealing with weighted requests can be extended to work for non-completeAOC problems such as Matching in the edge arrival model (giving better results than what follow from the generalAOC results) and even non-AOC problems such as scheduling.

1. For example, ⌈logn⌉could be written in unary (⌈logn⌉ones, followed by a zero) before writing n itself in binary.

2. f is a norm iff(αv) = |α|f(v),f(u +v) ≤f(u) +f(v), andf(v) = 0 ⇒v =0.

This work was partially supported by the Villum Foundation, grant VKR023219, and the Danish Council for Independent Research, Natural Sciences, grant DFF-1323-00247.

Authors and Affiliations

1. Department of Mathematics and Computer Science, University of Southern Denmark, 5230, Odense, Denmark

   Joan Boyar, Lene M. Favrholdt, Christian Kudahl & Jesper W. Mikkelsen

Corresponding author

Correspondence toJoan Boyar.

This article is part of the Topical Collection onSpecial Issue on Combinatorial Algorithms

A preliminary version of this paper appeared in the proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), Lecture Notes in Computer Science, vol. 9843, pp. 179–190, Springer (2016).

Appendix A: AOC-Complete Problems

For completeness, we state the full definition ofminASGk from [7]:

Definition 7 ([7])

The minimum asymmetric string guessing problem with known history,minASGk, has input 〈?,x₁,…,x_n〉, wherex =x₁…x_n ∈{0, 1}ⁿ, forsome\(n\in \mathbb {N}\).For 1 ≤i ≤n,round i proceeds as follows:

1. 1.

   Ifi > 1,the algorithm learns the correct answer,x_i−1,to the request in the previous round.

2. 2.

   The algorithm answersy_i =f(x₁,…,x_i−1) ∈{0, 1},where f is a function defined by the algorithm.

The outputy =y₁…y_ncomputed by thealgorithm is feasible, if\(x\sqsubseteq y\).Otherwise, y is infeasible. The cost of a feasible output is |y|₁, and the cost of aninfeasible output is∞.

In addition tominASGk, the class ofAOC-complete problems also contains many graph problems. The following four graph problems are studied in the vertex-arrival model, so the requests are vertices, each presented together with its edges to previous vertices. The first three problems are minimization problems and the last one is a maximization problem. InVertex Cover, an algorithm must accept a set of vertices which constitute a vertex cover, so for every edge in the requested graph, at least one of its endpoints is accepted. ForDominating Set, the accepted vertices must constitute a dominating set, so every vertex in the requested graph must be accepted, or one its neighbors must be accepted. InCycle Finding, an algorithm must accept a set of vertices inducing a cyclic graph. ForIndependent Set, the accepted vertices must form an independent set, i.e., no two accepted vertices share an edge.

ForDisjoint Path Allocation a pathP is given, and the requests are subpaths ofP. The aim is to accept as many edge disjoint paths as possible.

ForSet Cover, the requests are finite subsets from a known universe, and the union of the accepted subsets must be the entire universe. The aim is to accept as few subsets as possible.

Appendix B: Reductions for Theorem 2

In the proof of Theorem 2, a reduction sketch was given for the weighted online version of Vertex Cover. Here we include sketches for the reductions for the weighted versions of Cycle Finding, Dominating Set and Set Cover.

1.1Cycle Finding

Each inputσ = 〈x₁,x₂,…,x_n〉 to the problemminASGk, is transformed tof(σ) = 〈v₁,v₂,…,v_n〉, whereV = {v₁,v₂,…,v_n} is the vertex set of a graph with edge setE = {(v_j,v_i):f^′(x_i) =j}∪{(v_min,v_max)}, wheref^′(x_i) is the largestj <i such thatx_j = 1, max is the largesti such thatx_i = 1, and min is the smallesti such thatx_i = 1. If |σ|₁ > 2, the vertices corresponding to 1s form the only cycle in the graph.

The advice used by theminASGk algorithm Alg₁ consists of the advice used by the Cycle Finding algorithm Alg₂ in combination with 1 bit indicating whether or not |σ|₁ ≤ 2 and in this case (an encoding of) one or two indices of 1s in the input sequence. If |σ|₁ > 2, then Alg₂ accepts some vertices, and Alg₁ returns a 1 for thex_i corresponding to each of those vertices.

If Alg₁ returns a non-optimal feasible set, Alg₂ does too, and the sets have the same weights, so Alg₁(σ) ≤Alg₂(f(σ)) + Opt(σ). In this case, the weights of the optimal solutions forσ andf(σ) are both the sum of the weights of the elements corresponding to 1s inσ, sof is a length preservingO(f(n))-reduction.

1.2Dominating Set

Each inputσ = 〈x₁,x₂,…,x_n〉 to the problemminASGk, is transformed tof(σ) = 〈v₁,v₂,…,v_n〉, whereV = {v₁,v₂,…,v_n} is the vertex set of a graph with edge setE = {(v_i,v_max)}., where max is the largesti such thatx_i = 1.

The advice used by theminASGk algorithm Alg₁ consists of the advice used by the Dominating Set algorithm Alg₂ in combination with 1 bit indicating whether or not |σ|₁ = 0. If |σ|₁ ≥ 1, then there is another bit of advice indicating whether or not Alg₂ acceptedv_max. If Alg₂ did not acceptv_max, the advice also contains an index of a vertex corresponding to a 0 inσ which was accepted, plus the index ofv_max.

If Alg₁’s solution is feasible, but not optimal, then |σ|₁ > 0 and Alg₂ accepts some vertices, and Alg₁ returns a 1 for thex_i corresponding to each of those vertices (though, in the case wherev_max was rejected, it answers 1 forx_max and answers 0 for the earlier request indicated by the advice).

If |σ|₁ > 0 a minimum weight dominating set forf(σ) consists of exactly those vertices corresponding to 1s inσ, so the weights of the optimal solutions forσ andf(σ) are both the sum of the weights of the elements corresponding to 1s inσ, unless Alg₂ did not acceptv_max. However, the weight ofx_max ≤Opt(σ), so Alg₁(σ) ≤Alg₂(f(σ)) + Opt(σ). Thus,f is a length preservingO(log(n)-reduction.

1.3Set Cover

This reduction is very similar to that for Dominating Set. Each inputσ = 〈x₁,x₂,…,x_n〉 to the problemminASGk, max is the largesti such thatx_i = 1. In the set cover instance, the universe is {1,…,n}, andf(σ) is a set ofn requests, where requesti is {i}, unlessi = max, in which case, the set consists of max and all of thej wherex_j = 0.

As with the reduction to Dominating Set, this is a length preservingO(log(n)-reduction.

Reprints and permissions