標(biāo)題: Titlebook: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques; 11th International W Ashish Goel,Klaus Jansen,Ronit [打印本頁] 作者: Nutraceutical 時(shí)間: 2025-3-21 18:09
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques影響因子(影響力)
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques影響因子(影響力)學(xué)科排名
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques網(wǎng)絡(luò)公開度
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques網(wǎng)絡(luò)公開度學(xué)科排名
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques被引頻次
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques被引頻次學(xué)科排名
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques年度引用
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques年度引用學(xué)科排名
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques讀者反饋
書目名稱Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques讀者反饋學(xué)科排名
作者: shrill 時(shí)間: 2025-3-21 23:12 作者: curriculum 時(shí)間: 2025-3-22 00:41
Ordinal Embedding: Approximation Algorithms and Dimensionality Reductionst distances. More precisely, in an ordinal embedding, we must preserve the relative order between pairs of distances (which pairs are larger or smaller), and not necessarily the values of the distances themselves. The relaxation of an ordinal embedding is the maximum ratio between two distances who作者: arsenal 時(shí)間: 2025-3-22 06:44
Connected Vertex Covers in Dense Graphs results for this problem in dense graphs, in which either the minimum or the average degree is linear. In particular, we prove tight parameterized upper bounds on the approximation returned by Savage’s algorithm, and extend a vertex cover algorithm from Karpinski and Zelikovsky to the connected cas作者: 確定 時(shí)間: 2025-3-22 11:59 作者: 會議 時(shí)間: 2025-3-22 16:21 作者: thalamus 時(shí)間: 2025-3-22 20:06 作者: Fresco 時(shí)間: 2025-3-23 00:59 作者: Incumbent 時(shí)間: 2025-3-23 02:39
Approximating Maximum Subgraphs without Short Cyclesraph. The instance for these problems is a graph .?=?(.,.) and an integer .. The .. problem is to find a minimum edge subset of . that intersects every .-cycle. The .. problem is to find a maximum edge subset of . without .-cycles..The 3. problem (covering all triangles) was studied by Krivelevich [作者: 控制 時(shí)間: 2025-3-23 06:00 作者: ineptitude 時(shí)間: 2025-3-23 13:30
Inapproximability of Survivable Networksreserving reduction from . to .. Our reduction extends and widely generalizes as well as significantly simplifies the main results of [6]. Using it, we derive some new hardness of approximation results, as follows. We show that directed and undirected variants of . and of .. are equivalent w.r.t. ap作者: muffler 時(shí)間: 2025-3-23 17:30 作者: 不怕任性 時(shí)間: 2025-3-23 18:11 作者: organic-matrix 時(shí)間: 2025-3-24 00:32 作者: vanquish 時(shí)間: 2025-3-24 04:12
The Directed Minimum Latency Problemtencies at all vertices (the latency of any vertex .?∈?. is the distance from . to . along the path). This problem has been well-studied on symmetric metrics, and the best known approximation guarantee is 3.59 [3]. For any ., we give an .. time algorithm for directed latency that achieves an approxi作者: Inordinate 時(shí)間: 2025-3-24 07:16
A Simple LP Relaxation for the Asymmetric Traveling Salesman Problemman Problem (ATSP) is a constant. In this paper, we give a simpler LP relaxation for the ASTP. The integrality gaps of this relaxation and of the Held-Karp relaxation are within a constant factor of each other. Our LP is simpler in the sense that its extreme solutions have at most 2.???2 non-zero va作者: enmesh 時(shí)間: 2025-3-24 12:00
Approximating Directed Weighted-Degree Constrained Networkslems that seek to find a minimum cost . graph that satisfies both . connectivity requirements and . constraints. The input to such problems is a directed graph .?=?(.,.), edge-costs {.(.):.?∈?.}, edge-weights {.(.):.?∈?.}, an intersecting supermodular set-function . on ., and degree bounds {.(.):.?∈作者: 并入 時(shí)間: 2025-3-24 15:52 作者: 我的巨大 時(shí)間: 2025-3-24 19:50
Deterministic 7/8-Approximation for the Metric Maximum TSPThis improves over both the randomized algorithm of Hassin and Rubinstein [2] with expected approximation ratio of 7/8???.(..) and the deterministic (7/8???.(..))-approximation algorithm of Chen and Nagoya [1]..In the new algorithm, we extend the approach of processing local configurations using so-called loose-ends, which we introduced in [4].作者: Nucleate 時(shí)間: 2025-3-25 01:15
Springer Tracts in Modern Physics 21tems .?=?(.., ..., ..). The goal is to output a binary tree where each internal node is a test, each leaf is an item and the total external path length of the tree is minimized. Total external path length is the sum of the depths of all the leaves in the tree. DT has a long history in computer scien作者: amyloid 時(shí)間: 2025-3-25 07:04
Springer Tracts in Modern Physics . items, each of which associated with a non-negative value. There are also . players and each player is only interested in some of the items. The goal is to distribute the items between the players such that the least happy person is as happy as possible, i.e. one wants to maximize the minimum of 作者: 男學(xué)院 時(shí)間: 2025-3-25 10:56 作者: 鉤針織物 時(shí)間: 2025-3-25 12:39 作者: indignant 時(shí)間: 2025-3-25 19:24 作者: 起皺紋 時(shí)間: 2025-3-25 23:57 作者: Neuralgia 時(shí)間: 2025-3-26 01:11
Springer Tracts in Modern Physics 17ques of Samorodnitsky and Trevisan [19] to obtain a UGC hardness result when . is a prime. More precisely, assuming the Unique Games Conjecture, we show that it is NP-hard to approximate the problem to a ratio greater than .../... Independent of this work, Austrin and Mossel [2] obtain a more genera作者: myopia 時(shí)間: 2025-3-26 05:08 作者: DEFT 時(shí)間: 2025-3-26 12:18
Springer Tracts in Modern Physicsraph. The instance for these problems is a graph .?=?(.,.) and an integer .. The .. problem is to find a minimum edge subset of . that intersects every .-cycle. The .. problem is to find a maximum edge subset of . without .-cycles..The 3. problem (covering all triangles) was studied by Krivelevich [作者: 讓步 時(shí)間: 2025-3-26 13:05
https://doi.org/10.1007/BFb0111918This improves over both the randomized algorithm of Hassin and Rubinstein [2] with expected approximation ratio of 7/8???.(..) and the deterministic (7/8???.(..))-approximation algorithm of Chen and Nagoya [1]..In the new algorithm, we extend the approach of processing local configurations using so-作者: Crohns-disease 時(shí)間: 2025-3-26 19:04
Springer Tracts in Modern Physics 6reserving reduction from . to .. Our reduction extends and widely generalizes as well as significantly simplifies the main results of [6]. Using it, we derive some new hardness of approximation results, as follows. We show that directed and undirected variants of . and of .. are equivalent w.r.t. ap作者: 智力高 時(shí)間: 2025-3-27 00:24
Springer Tracts in Modern Physics 6ers. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in the definition of the instance. We study the single machine scheduling problem with the objective to minimize the weighted sum of completion times. We model uncertainty by replacing the vector 作者: 走路左晃右晃 時(shí)間: 2025-3-27 02:10 作者: Spinal-Tap 時(shí)間: 2025-3-27 07:12
Springer Tracts in Modern Physics 14ich more than one objective function are combined into one using any norm. The main idea is to exploit the approximate Pareto-optimal frontier for multi-criteria optimization problems. Using this approach, we obtain an FPTAS for a novel resource allocation problem, for the problem of scheduling jobs作者: 成績上升 時(shí)間: 2025-3-27 11:19 作者: Resection 時(shí)間: 2025-3-27 16:21
Springer Tracts in Modern Physics 14man Problem (ATSP) is a constant. In this paper, we give a simpler LP relaxation for the ASTP. The integrality gaps of this relaxation and of the Held-Karp relaxation are within a constant factor of each other. Our LP is simpler in the sense that its extreme solutions have at most 2.???2 non-zero va作者: FOLD 時(shí)間: 2025-3-27 18:58 作者: euphoria 時(shí)間: 2025-3-28 00:32 作者: 驕傲 時(shí)間: 2025-3-28 02:13
https://doi.org/10.1007/978-3-540-85363-3algorithms; anonymity; approximation; approximation algorithms; black-box reductions; clustering; coding; c作者: FLAG 時(shí)間: 2025-3-28 09:42
978-3-540-85362-6Springer-Verlag Berlin Heidelberg 2008作者: Delude 時(shí)間: 2025-3-28 14:26 作者: 配偶 時(shí)間: 2025-3-28 16:22 作者: 引起 時(shí)間: 2025-3-28 21:47
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/b/image/160455.jpg作者: Eructation 時(shí)間: 2025-3-29 00:18
https://doi.org/10.1007/BFb0112094We consider the deadline problem and budget problem of the nonlinear time-cost tradeoff project scheduling model in a series-parallel activity network. We develop fully polynomial time approximation schemes for both problems using .-approximation sets and functions, together with series and parallel reductions.作者: 音樂戲劇 時(shí)間: 2025-3-29 05:09
Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel ProjeWe consider the deadline problem and budget problem of the nonlinear time-cost tradeoff project scheduling model in a series-parallel activity network. We develop fully polynomial time approximation schemes for both problems using .-approximation sets and functions, together with series and parallel reductions.作者: 不妥協(xié) 時(shí)間: 2025-3-29 08:48
Springer Tracts in Modern Physicsrovide a polynomial time algorithm for finding an allocation. In this paper, we take a different approach to this problem, based upon local search techniques for finding perfect matchings in certain classes of hypergraphs. As a result, we prove that the integrality gap of the configuration LP is bou作者: enflame 時(shí)間: 2025-3-29 13:56
Springer Tracts in Modern Physics 20ng the way, we improve the best known approximation factor for ordinally embedding unweighted trees into the line down to?2. Our results illustrate an important contrast to optimal-distortion metric embeddings, where the best approximation factor for unweighted graphs into the line is .(..), and eve作者: Servile 時(shí)間: 2025-3-29 18:24 作者: Flirtatious 時(shí)間: 2025-3-29 23:10
Springer Tracts in Modern Physics 6hted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6/5. We conclude by presenting a polynomial time algorithm based on dynamic programmi作者: 做方舟 時(shí)間: 2025-3-30 00:04
SCHRIFTLEITUNG DER NATURWISSENSCHAFTEN weighted completion time in .. We note that even in unweighted directed graphs, the directed latency problem is at least as hard to approximate as the well-studied ., for which the best known approximation guarantee is .(log.).作者: BRAND 時(shí)間: 2025-3-30 05:29
Springer Tracts in Modern Physics 5nd weighted degrees ≤?6 .(.). We obtain similar results when there are both indegree and outdegree constraints, and better results when there are indegree constraints only: a (1,4)-approximation algorithm for arbitrary weights and a polynomial time algorithm for unit weights. Finally, we consider th作者: 山羊 時(shí)間: 2025-3-30 08:54
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques11th International W作者: 脾氣暴躁的人 時(shí)間: 2025-3-30 13:09 作者: CRASS 時(shí)間: 2025-3-30 16:31 作者: 初學(xué)者 時(shí)間: 2025-3-30 23:19 作者: 老巫婆 時(shí)間: 2025-3-31 03:56
Approximating Maximum Subgraphs without Short Cycless a (.???1)-approximation algorithm, which extends the result of Krivelevich from .?=?3 to any .. Based on this, for odd . we give an algorithm for .. with ratio .; this improves over the trivial ratio of 1/2..Our main result however is for the .. problem with even values of .. For any .?=?2., we gi作者: 牌帶來 時(shí)間: 2025-3-31 06:12
Approximating Single Machine Scheduling with Scenarioshted case. We show that our analysis is tight by providing a matching lower bound on the integrality gap of the LP. Moreover, we prove that the unweighted version is NP-hard to approximate within a factor less than 6/5. We conclude by presenting a polynomial time algorithm based on dynamic programmi作者: Decimate 時(shí)間: 2025-3-31 12:10 作者: 令人發(fā)膩 時(shí)間: 2025-3-31 15:47 作者: 手工藝品 時(shí)間: 2025-3-31 18:37
Conference proceedings 2008lona (1998), Berkeley (1999), Geneva (2000), Berkeley (2001), Harvard (2002), Princeton (2003), Cambridge (2004), Berkeley (2005), Barcelona (2006), and Princeton (2007). Topics of interest for APPROX and RANDOM are: design and analysis of - proximation algorithms, hardness of approximation, small s作者: 真實(shí)的你 時(shí)間: 2025-4-1 01:33
0302-9743 lems (APPROX 2008) and the 12th International Workshop on Randomization and Computation (RANDOM 2008), which took place concurrently at the MIT (M- sachusetts Institute of Technology) in Boston, USA, during August 25–27, 2008. APPROX focuses on algorithmic and complexity issues surrounding the devel作者: Esalate 時(shí)間: 2025-4-1 05:08 作者: instulate 時(shí)間: 2025-4-1 08:52
Inapproximability of Survivable Networkse derive some new hardness of approximation results, as follows. We show that directed and undirected variants of . and of .. are equivalent w.r.t. approximation, and that a .-approximation for . implies a .-approximation for ..作者: arbovirus 時(shí)間: 2025-4-1 12:38
Trennungsenergien einzelner Bindungen,ts are shown to be tight. Finally, we introduce the . for the vertex cover problem, defined as the worst-case ratio between the sizes of a minimum connected vertex cover and a minimum vertex cover. We prove that the price of connectivity is bounded by 2/(1?+?.) in graphs with average degree ., and give a family of near-tight examples.作者: 建筑師 時(shí)間: 2025-4-1 16:16
Die Schlierenverfahren und ihre Anwendungen,gorithm. Here we present a ratio 4/.?≈?1.27 approximation algorithm in the length measure, which performs at most four sweeps. We also prove that, for the two constrained variants, there are sets of . points for which any sequence of minimum cost requires 3./2???.(1) sweeps.作者: 精致 時(shí)間: 2025-4-1 21:16
