We analyze the Disjoint Path Allocation problem (DPA) in the priority framework. Motivated by the problem of traffic regulation in communication networks, DPA consists of allocating edge-disjoint paths in a graph. Lik...
详细信息
We analyze the Disjoint Path Allocation problem (DPA) in the priority framework. Motivated by the problem of traffic regulation in communication networks, DPA consists of allocating edge-disjoint paths in a graph. Like an online algorithm, a priority algorithm receives its input sequentially and must output irrevocable decisions for individual input items before having seen the entire input. However, in contrast to the online setting, a priority algorithm may choose an order on the set of all possible input items and the actual input is then presented according to this order. A priority algorithm is thus a natural model for the intuitively well-understood concept of a greedy algorithm. Mainly motivated by their application for proving lower bounds, we also consider priority algorithms with advice, thus measuring the necessary amount of information about the yet unknown parts of the input. Besides considering the classical variant of the DPA problem on paths and the related problem of Length-Weighted DPA, we mainly focus on DPA on trees. We show asymptotically matching upper and lower bounds on the advice necessary for optimality in LWDPA and generalize the known optimality result for DPA on paths to trees with maximal degree at most 3. On trees with higher maximal degree, we prove matching upper and lower bounds on the approximation ratio in the advice-free priority setting as well as upper and lower bounds on the advice necessary to achieve optimality.
We continue the study of priority or "greedy-like" algorithms as initiated in Borodin et al. (2003) [10] and as extended to graph theoretic problems in Davis and Impagliazzo (2009) [12]. Graph theoretic prob...
详细信息
We continue the study of priority or "greedy-like" algorithms as initiated in Borodin et al. (2003) [10] and as extended to graph theoretic problems in Davis and Impagliazzo (2009) [12]. Graph theoretic problems pose some modeling problems that did not exist in the original applications of Borodin et al. and Angelopoulos and Borodin (2002) [3]. Following the work of Davis and Impagliazzo, we further clarify these concepts. In the graph theoretic setting, there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known "greedy algorithms". (C) 2009 Elsevier B.V. All rights reserved.
The priority model of "greedy-like" algorithms was introduced by Borodin, Nielsen, and Rackoff in 2002. We augment this model by allowing priority algorithms to have access to advice, i.e., side information ...
详细信息
The priority model of "greedy-like" algorithms was introduced by Borodin, Nielsen, and Rackoff in 2002. We augment this model by allowing priority algorithms to have access to advice, i.e., side information precomputed by an all-powerful oracle. Obtaining lower bounds in the priority model without advice can be challenging and may involve intricate adversary arguments. Since the priority model with advice is even more powerful, obtaining lower bounds presents additional difficulties. We sidestep these difficulties by developing a general framework of reductions which makes lower bound proofs relatively straightforward and routine. We start by introducing the Pair Matching problem, for which we are able to prove strong lower bounds in the priority model with advice. We develop a template for constructing a reduction from Pair Matching to other problems in the priority model with advice - this part is technically challenging since the reduction needs to define a valid priority function for Pair Matching while respecting the priority function for the other problem. Finally, we apply the template to obtain lower bounds for a number of standard discrete optimization problems.
The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice,...
详细信息
The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.
We study the question of which optimization problems can be optimally or approximately solved by "greedy-like" algorithms. For definiteness, we limit the present discussion to some well-studied scheduling pr...
详细信息
We study the question of which optimization problems can be optimally or approximately solved by "greedy-like" algorithms. For definiteness, we limit the present discussion to some well-studied scheduling problems although the underlying issues apply in a much more general setting. Of course, the main benefit of greedy algorithms lies in both their conceptual simplicity and their computational efficiency. Based on the experience from online competitive analysis, it seems plausible that we should be able to derive approximation bounds for "greedy-like" algorithms exploiting only the conceptual simplicity of these algorithms. To this end, we need (and will provide) a precise definition of what we mean by greedy and greedy-like.
The large-scale integration of electric vehicles (EVs) into modern power grid brings both challenges and opportunities to the performance of the systems. This paper presents an optimal static (when EV is stationary) c...
详细信息
The large-scale integration of electric vehicles (EVs) into modern power grid brings both challenges and opportunities to the performance of the systems. This paper presents an optimal static (when EV is stationary) charging scheduling scheme of EVs to minimize the charging cost while complying with the constraints related to the status of the charging station. The proposed systematic charging scheme is based on "Particle Swarm Optimization (PSO)". It is compared with well-established algorithms such as "Arrival Time-Based priority (ATP) algorithm" and "SOC-Based priority (SBP) algorithm". In addition, a microgrid scenario is further considered for reducing the consumption of energy from the grid and also, reducing the charging cost by properly shifting the EV load. Based on the study carried out for a sample test cases considered, it is found that the proposed scheme has better performance compared to the existing schemes.
We introduce BubbleScarch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign va...
详细信息
We introduce BubbleScarch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign values to elements in some fixed or adaptively determined order. BubbleSearch extends priority algorithms by selectively considering additional orders near an initial good ordering. While many notions of nearness are possible, we explore algorithms based on the Kendall-tau distance (also known as the BubbleSort distance) between permutations. Our contribution is to elucidate the BubbleSearch paradigm and experimentally demonstrate its effectiveness. (c) 2005 Published by Elsevier B.V.
Since Tinhofer proposed the MINGREEDY algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and ben...
详细信息
Since Tinhofer proposed the MINGREEDY algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and benchmark instances. In contrast, only few analytical results are known. We show that MINGREEDY cannot improve on the trivial approximation ratio of 1/2 whp., even for bipartite graphs. Our hard inputs seem to require a small number of high-degree nodes. This motivates an investigation of greedy algorithms on graphs with maximum degree Delta: we show that MINGREEDY achieves a Delta-1/2 Delta-3-approximation for graphs with Delta=3 and for Delta-regular graphs, and a guarantee of Delta-1/2/2 Delta-2 for graphs with maximum degree Delta. Interestingly, our bounds even hold for the deterministic MINGREEDY that breaks all ties arbitrarily. Moreover, we investigate the limitations of the greedy paradigm, using the model of priority algorithms introduced by Borodin, Nielsen, and Rackoff. We study deterministic priority algorithms and prove a Delta-1/2 Delta-3 -inapproximability result for graphs with maximum degree Delta;thus, these greedy algorithms do not achieve a 1/2+epsilon-approximation and in particular the 2/3-approximation obtained by the deterministic MINGREEDY for Delta=3 is optimal in this class. For k-uniform hypergraphs we show a tight 1/k-inapproximability bound. We also study fully randomized priority algorithms and give a 5/6-inapproximability bound. Thus, they cannot compete with matching algorithms of other paradigms.
The "priority Algorithm" is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) priority algorithms, Algorithmica 37(4): 295-326, 2003) which formulates a wide class of greedy al...
详细信息
The "priority Algorithm" is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) priority algorithms, Algorithmica 37(4): 295-326, 2003) which formulates a wide class of greedy algorithms. For an arbitrary set S of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of S. In the case where the jobs are all intervals, we characterize such sets S and give an efficient algorithm (when S is finite) for determining this. We show that in general, however, the problem is NP-hard.
We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a 3/4-approximation in expectation. In contrast to previously known 3/4-approximation algorithms, our algorit...
详细信息
We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a 3/4-approximation in expectation. In contrast to previously known 3/4-approximation algorithms, our algorithm does not use flows or linear programming. Hence we provide a positive answer to a question posed by Williamson in 1998 on whether such an algorithm exists. Moreover, we show that Johnson's greedy algorithm cannot guarantee a 3/4-approximation, even if the variables are processed in a random order. Thereby we partially solve a problem posed by Chen, Friesen, and Zheng in 1999. In order to explore the limitations of the greedy paradigm, we use the model of priority algorithms of Borodin, Nielsen, and Rackoff. Since our greedy algorithm works in an online scenario where the variables arrive with their set of undecided clauses, we wonder if a better approximation ratio can be obtained by further fine-tuning its random decisions. For a particular information model we show that no priority algorithm can approximate Online MAX SAT within 3/4 + epsilon (for any epsilon > 0). We further investigate the strength of deterministic greedy algorithms that may choose the variable ordering. Here we show that no adaptive priority algorithm can achieve approximation ratio 3/4. We propose two ways in which this inapproximability result can be bypassed. First we show that if our greedy algorithm is additionally given the variable assignments of an optimal solution to the canonical LP relaxation, then we can derandomize its decisions while preserving the overall approximation guarantee. Second we give a simple, deterministic algorithm that performs an additional pass over the input. We show that this 2-pass algorithm satisfies clauses with a total weight of at least 3/4 OPTLP, where OPTLP is the objective value of the canonical linear program. Moreover, we demonstrate that our analysis is tight and detail how each pass can be implemented in linear time.
暂无评论