標題: Titlebook: Approximation Algorithms for Combinatorial Optimization; Third International Klaus Jansen,Samir Khuller Conference proceedings 2000 Spring [打印本頁] 作者: antibody 時間: 2025-3-21 16:09
書目名稱Approximation Algorithms for Combinatorial Optimization影響因子(影響力)
書目名稱Approximation Algorithms for Combinatorial Optimization影響因子(影響力)學(xué)科排名
書目名稱Approximation Algorithms for Combinatorial Optimization網(wǎng)絡(luò)公開度
書目名稱Approximation Algorithms for Combinatorial Optimization網(wǎng)絡(luò)公開度學(xué)科排名
書目名稱Approximation Algorithms for Combinatorial Optimization被引頻次
書目名稱Approximation Algorithms for Combinatorial Optimization被引頻次學(xué)科排名
書目名稱Approximation Algorithms for Combinatorial Optimization年度引用
書目名稱Approximation Algorithms for Combinatorial Optimization年度引用學(xué)科排名
書目名稱Approximation Algorithms for Combinatorial Optimization讀者反饋
書目名稱Approximation Algorithms for Combinatorial Optimization讀者反饋學(xué)科排名
作者: zonules 時間: 2025-3-21 22:12
,Einführung in die Problemstellung,approximation algorithm for solving the problem. The algorithm is based on exploiting structural properties of basic solutions to a linear relaxation in combination with the pipage rounding technique developed in some earlier papers by two of the authors.作者: 格言 時間: 2025-3-22 02:11 作者: Isthmus 時間: 2025-3-22 07:36 作者: GRACE 時間: 2025-3-22 11:36 作者: FEAT 時間: 2025-3-22 13:59 作者: UNT 時間: 2025-3-22 17:14
Approximation Algorithms That Take Adviceertheless, this is a useful way of thinking about some approximation algorithms. In the talk I will present a few examples. My title is a play on the title of a classic paper on nonuniform computation “Turing Machines that take advice” (Karp and Lipton 1982).作者: 泥瓦匠 時間: 2025-3-22 23:02
Instant Recognition of Polynomial Time Solvability, Half Integrality, and 2-Approximationshe problem is NP-hard the technique is used to generate superoptimal solution all components of which are integer multiple of . In some of the latter cases, for minimization problems, the half integral solution may be rounded to a feasible solution that is provably within a factor of 2 of the optimum.作者: Presbyopia 時間: 2025-3-23 04:35 作者: 同音 時間: 2025-3-23 08:52
Wavelength Rerouting in Optical Networks, or the Venetian Routing Problempaths. In this paper we prove the computational hardness oft his problem even in various special cases, and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover.作者: 猜忌 時間: 2025-3-23 11:19
Greedy Approximation Algorithms for Finding Dense Components in a Graph of finding subgraphs maximizing these notions of density for undirected and directed graphs. This paper gives simple greedy approximation algorithms for these optimization problems. We also answer an open question about the complexity of the optimization problem for directed graphs.作者: 多產(chǎn)魚 時間: 2025-3-23 16:31 作者: FLIC 時間: 2025-3-23 18:39
https://doi.org/10.1007/978-3-8349-9978-8ingle edge was known. We extend the problem in several new directions: continuous metrics, variable size requests, andre plication before service. Finally, we give simplified proofs of several known results.作者: browbeat 時間: 2025-3-24 00:15 作者: employor 時間: 2025-3-24 04:44
On the Relative Complexity of Approximate Counting Problemsty. We describe and investigate not only these two classes but also a third class, of intermediate complexity, that is not known to be identical to (i) or (ii). The third class can be characterised as the hardest problems in a logically defined subclass of #P.作者: 漸強 時間: 2025-3-24 09:58 作者: 600 時間: 2025-3-24 13:38 作者: mucous-membrane 時間: 2025-3-24 17:01
Erfolgsfaktoren im Stiftungsmanagementertheless, this is a useful way of thinking about some approximation algorithms. In the talk I will present a few examples. My title is a play on the title of a classic paper on nonuniform computation “Turing Machines that take advice” (Karp and Lipton 1982).作者: 承認 時間: 2025-3-24 19:11 作者: sperse 時間: 2025-3-25 00:47
https://doi.org/10.1007/978-3-8349-8456-2alient ideas in these algorithms and their analyzes are simple-to-explain and reflect a surprising degree of commonality. This note is intended as companion to our lecture at CONF 2000, mainly to give pointers to the appropriate references.作者: 逗它小傻瓜 時間: 2025-3-25 04:45 作者: menopause 時間: 2025-3-25 11:30 作者: 碳水化合物 時間: 2025-3-25 12:51
Die Ergebnisse der Empirischen Untersuchung,the multiprocessor case while maintaining constant competitiveness. The multiprocessor algorithm does not use migration, i.e., preempted jobs continue their execution on the same processor on which they were originally processed.作者: 確定方向 時間: 2025-3-25 16:15
Erfolgsfaktoren in Filialsystemenly it was shown VLSP-[0, .) is NP-hard and that VLSP-{1, 2} can be solved efficiently. For a more general case of VLSP-{1, .} an 2 - 1/. approximation was shown. This paper shows that for . ≥ 3 VLSP-{1, .} is MAX-SNP hard, and that we can approximate it with ratio 2 - 4/(. + 3).作者: 天空 時間: 2025-3-25 21:08
https://doi.org/10.1007/978-3-8349-9978-8m an optimal solution is substantially closer than what one would obtain by just taking a random solution. In fact, we have been able to show similar results for most of Karp’s 21 original .-complete problems. (At the moment, our results are not tight only for UNDIRECTED HAMILTONIAN CYCLE and FEEDBACK EDGE SET.)作者: ovation 時間: 2025-3-26 02:04 作者: Inveterate 時間: 2025-3-26 04:53
https://doi.org/10.1007/978-3-8349-9978-8) where ρST is the performance ratio of any approximation algorithm for minimum Steiner tree. When all sources have the same demand value, the ratio improves to (nST +1) and in particular, to 2 when all nodes in the graph are sources.作者: Offensive 時間: 2025-3-26 10:10 作者: Connotation 時間: 2025-3-26 16:23 作者: FECT 時間: 2025-3-26 19:22 作者: 涂掉 時間: 2025-3-26 21:21
Maximum Dispersion and Geometric Maximum Weight Cliques have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where . is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where . is part of the input, we present a polynomial-time approximation scheme.作者: largesse 時間: 2025-3-27 03:44
Approximation Algorithms for a Capacitated Network Design Problem) where ρST is the performance ratio of any approximation algorithm for minimum Steiner tree. When all sources have the same demand value, the ratio improves to (nST +1) and in particular, to 2 when all nodes in the graph are sources.作者: geriatrician 時間: 2025-3-27 08:44
https://doi.org/10.1007/978-3-663-13438-1s of greedy algorithms that use randomization. We study their limitations and prove that, with high probability, randomized greedy algorithms cannot achieve a performance ratio better than 3/2 when applied to binary trees of depth Ω(.), and 1.293 - o(1) when applied to binary trees of constant depth作者: chemoprevention 時間: 2025-3-27 12:16
https://doi.org/10.1007/978-3-8349-9978-8ive ratio of any online algorithm as the ratio of the value of the objective function obtained by this algorithm to that of the best possible offline algorithm. We show that no online algorithm can have a competitive ratio greater than 1-(1/α)+ε for hard real-time scheduling with K ≥ 1 machines and 作者: ANT 時間: 2025-3-27 17:06
Approximation Algorithms for Combinatorial OptimizationThird International 作者: FECT 時間: 2025-3-27 18:04
Randomized Path Coloring on Binary Treess of greedy algorithms that use randomization. We study their limitations and prove that, with high probability, randomized greedy algorithms cannot achieve a performance ratio better than 3/2 when applied to binary trees of depth Ω(.), and 1.293 - o(1) when applied to binary trees of constant depth作者: LINE 時間: 2025-3-28 00:37
Online Real-Time Preemptive Scheduling of Jobs with Deadlinesive ratio of any online algorithm as the ratio of the value of the objective function obtained by this algorithm to that of the best possible offline algorithm. We show that no online algorithm can have a competitive ratio greater than 1-(1/α)+ε for hard real-time scheduling with K ≥ 1 machines and 作者: 起來了 時間: 2025-3-28 04:10 作者: 你不公正 時間: 2025-3-28 08:13 作者: 變色龍 時間: 2025-3-28 11:29
https://doi.org/10.1007/978-3-8349-8456-2occur during project execution. A typical con- sequence is the underestimation of the expected project duration and cost frequently observed in practice. To cope with these phenomena, we consider schedulingmodels in which processingtimes are random but precedence and resource constraints are fixed. 作者: Serenity 時間: 2025-3-28 16:40 作者: Spongy-Bone 時間: 2025-3-28 20:01
,Einführung in die Problemstellung,) with maximum total weight. In this paper we consider a version of max dicut — max dicut with given sizes of parts or max dicut with gsp — whose instance is that of max dicut plus a positive integer p, and it is required to find a directed cut δ(X) having maximum weight over all cuts δ(X) with |X| 作者: 大火 時間: 2025-3-29 00:31
Die Ergebnisse der Empirischen Untersuchung,ves with its own execution time and its benefit function. The flow time of a job is the time that passes from its release to its completion. The benefit function specifies the benefit gained for any given flow time. A scheduler’s goal is to maximize the total gained benefit. We present a constant co作者: Coma704 時間: 2025-3-29 05:05
Erfolgsfaktoren in Filialsystemen Problem, or VLSP-L. Let [.) denote .+1, ..., .- 1. The problem is given by a set of jobs J and the time-dependent length function λ : . × [0, n) → L. A sequencing function σ : . →[0, .) assigns to each job j a time interval τ.(j) when this job is executed; if σ(.) = t then τσ(.) = [.+λ(.)). The seq作者: cuticle 時間: 2025-3-29 07:23 作者: 掃興 時間: 2025-3-29 13:14
Theoretisches Modell und Hypothesenbildung,sion Multiplexing (WDM) networks. This method leads to the following combinatorial optimization problem, dubbed Venetian Routing. Given a . along with two vertices s and . and a collection of pairwise arc-disjoint paths, we wish to find an .-path which arc-intersects the smallest possible . of such 作者: Innovative 時間: 2025-3-29 18:24
Theoretisches Modell und Hypothesenbildung,ph we use is the average degree of the subgraph. For directed graphs, a corresponding notion of density was introduced recently by Kannan and Vinay. This is designed to quantify highly connectedness of substructures in a sparse directed graph such as the web graph. We study the optimization problems作者: engrossed 時間: 2025-3-29 19:57
https://doi.org/10.1007/978-3-8349-9978-8s when jobs are characterized in terms of their minimum stretchf actor α (or, equivalently, their maximum execution rate . = 1/α). We consider two well known preemptive models that are of interest from practical applications: the . model in which a job must be completed if it was admitted for execut作者: AUGER 時間: 2025-3-30 03:06 作者: 手段 時間: 2025-3-30 05:11 作者: 蒸發(fā) 時間: 2025-3-30 10:48 作者: Graphite 時間: 2025-3-30 14:57 作者: objection 時間: 2025-3-30 18:14 作者: NUDGE 時間: 2025-3-30 23:38
https://doi.org/10.1007/978-3-8349-9978-8s to a sink and to install capacity on the edges to support flows at minimum cost. Capacity can be purchased only in multiples of a fixed quantity. All the flow from a source must be routed in a single path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more effectiv作者: 熒光 時間: 2025-3-31 01:30
https://doi.org/10.1007/978-3-663-07644-5give the first non-trivial approximation algorithm for this problem, having an approximation guarantee of 3·H., where . is the maximum requirement and H. is the k-th harmonic number. Our algorithm is along the lines of [.] for the generalized Steiner network problem. It runs in phases, and each phas作者: indicate 時間: 2025-3-31 06:29
Theoretische Herleitung der Hypothesendórsson and Hassin (Information Processing Letters 47:275-282, 1993) give approximation algorithms with ratio 3.55 (tree cover) and 5.5 (tour cover). We present algorithms with worst-case ratio 3 for both problems.作者: 詞根詞綴法 時間: 2025-3-31 11:53 作者: 煩憂 時間: 2025-3-31 13:49
Improved Approximations for Tour and Tree Coversdórsson and Hassin (Information Processing Letters 47:275-282, 1993) give approximation algorithms with ratio 3.55 (tree cover) and 5.5 (tour cover). We present algorithms with worst-case ratio 3 for both problems.作者: FLEET 時間: 2025-3-31 18:52 作者: 聚集 時間: 2025-3-31 22:37 作者: engrave 時間: 2025-4-1 04:18
Approximation Algorithms for Combinatorial Optimization978-3-540-44436-7Series ISSN 0302-9743 Series E-ISSN 1611-3349
