the proceedings contain 26 papers. the topics discussed include: approximationalgorithms for scheduling problems with exact delays;coping with interference: from maximum coverage to planning cellular networks;online ...
详细信息
ISBN:
(纸本)9783540695134
the proceedings contain 26 papers. the topics discussed include: approximationalgorithms for scheduling problems with exact delays;coping with interference: from maximum coverage to planning cellular networks;online dynamic programming speedups;covering many of few points with unit disks;on the minimum corridor problem and other generalized geometric problems;improved approximation bounds for edge dominating set in dense graphs;a randomized algorithm for online unit clustering;on hierarchical diameter-clustering, and the supplier problem;on bin packing with conflicts;approximate distance queries in disk graphs;network design with edge-connectivity and degree constraints;approximating maximum cut with limited unbalance;worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems;and an experimental study of the misdirection algorithm for combinatorial auctions.
the proceedings contain 22 papers. the topics discussed include: independent set with advice: the impact of graph knowledge;online multi-commodity flow with high demands;on the complexity of the regenerator location p...
ISBN:
(纸本)9783642380150
the proceedings contain 22 papers. the topics discussed include: independent set with advice: the impact of graph knowledge;online multi-commodity flow with high demands;on the complexity of the regenerator location problem - treewidth and other parameters;online exploration of polygons with holes;on minimum-and maximum-weight minimum spanning trees with neighborhoods;asymptotically optimal online page migration on three points;R-LINE: a better randomized 2-server algorithm on the line;competitive-ratio approximation schemes for makespan scheduling problems;online primal-dual for non-linear optimization with applications to speed scaling;approximating the throughput by coolest first scheduling;a unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games;improved approximation guarantees for lower-bounded facility location;and a 4-approximation for the height of drawing 2-connected outer-planar graphs.
the proceedings contain 16 papers. the special focus in this conference is on approximation and onlinealgorithms. the topics include: FIFO and Randomized Competitive Packet Routing Games;improved online Algorith...
ISBN:
(纸本)9783030927011
the proceedings contain 16 papers. the special focus in this conference is on approximation and onlinealgorithms. the topics include: FIFO and Randomized Competitive Packet Routing Games;improved online Algorithm for Fractional Knapsack in the Random Order Model;fractionally Subadditive Maximization Under an Incremental Knapsack Constraint;improved Analysis of online Balanced Clustering;precedence-Constrained Covering Problems with Multiplicity Constraints;contention Resolution, Matrix Scaling and Fair Allocation;constant Factor approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set;an Improved approximation Bound for Minimum Weight Dominating Set on Graphs of Bounded Arboricity;tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems;on b-Matchings and b-Edge Dominating Sets: A 2-approximation Algorithm for the 4-Edge Dominating Set Problem;the Traveling k-Median Problem: Approximating Optimal Network Coverage;EPTAS for Load Balancing Problem on Parallel Machines with a Non-renewable Resource;several Methods of Analysis for Cardinality Constrained Bin Packing;weighted Completion Time Minimization for Capacitated Parallel Machines.
the proceedings contain 32 papers. the special focus in this conference is on APPROX and RANDOM. the topics include: Using complex semidefinite programming for approximating MAX E2-LIN3;hill-climbing vs. simulated ann...
ISBN:
(纸本)3540424709
the proceedings contain 32 papers. the special focus in this conference is on APPROX and RANDOM. the topics include: Using complex semidefinite programming for approximating MAX E2-LIN3;hill-climbing vs. simulated annealing for planted bisection problems;web search via hub synthesis;error-correcting codes and pseudorandom projections;order in pseudorandomness;minimizing stall time in single and parallel disk systems using multicommodity network flows;on the equivalence between the primal-dual schema and the local-ratio technique;online weighted flow time and deadline scheduling;an online algorithm for the postman problem with a small penalty;a simple dual ascent algorithm for the multilevel facility location problem;approximation schemes for ordered vector packing problems;incremental codes;a 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set;approximationalgorithms for budget-constrained auctions;minimizing average completion of dedicated tasks and interval graphs;a greedy facility location algorithm analyzed using dual fitting;0.863-approximation algorithm for MAX DICUT;the maximum acyclic subgraph problem and degree-3 graphs;some approximation results for the maximum agreement forest problem;near-optimum universal graphs for graphs with bounded degrees;on a generalized ruin problem;on the b-partite random asymmetric traveling salesman problem and its assignment relaxation;exact sampling in machine scheduling problems;on computing ad-hoc selective families and l infinity embeddings.
Given a data set in a metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter, and the hierarchical k-supplier problem with customers arriving online. We prove that two p...
详细信息
Given a data set in a metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter, and the hierarchical k-supplier problem with customers arriving online. We prove that two previously known algorithms for hierarchical clustering, one (offline) due to Dasgupta and Long and the other (online) due to Charikar, Chekuri, Feder and Motwani, output essentially the same result when points are considered in the same order. We show that the analyses of bothalgorithms are tight and exhibit a new lower bound for hierarchical clustering. Finally we present the first constant factor approximation algorithm for the online hierarchical k-supplier problem.
We present new combinatorial approximationalgorithms for the k-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. the new algorithms further extend ...
详细信息
We present new combinatorial approximationalgorithms for the k-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. the new algorithms further extend these approaches by utilizing the natural idea of computing large packings of elements into sets of large size. Our results improve the previously best approximation bounds for the k-set cover problem for all values of ka parts per thousand yen6. the analysis technique used could be of independent interest;the upper bound on the approximation factor is obtained by bounding the objective value of a factor-revealing linear program.
In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensiona...
详细信息
In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the na < ve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.
We analyze approximationalgorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with gamma-triangle inequality. For this proble...
详细信息
We analyze approximationalgorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with gamma-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of min{1 + gamma, 2 gamma(2)/2 gamma(2) - 2 gamma+1} + epsilon and a randomized approximation algorithm that achieves a ratio of 2 gamma(3)+2 gamma(2)/3 gamma(2)-2 gamma+1 + epsilon. In particular, we obtain a 2 + e approximation for multi-criteria metric STSP. then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximationalgorithms for STSP with. - triangle inequality ( ratio 1+gamma/1+3 gamma-4 gamma(2) + epsilon), asymmetric TSP (ATSP) with. - triangle inequality ( ratio 1/2 + gamma(3)/1-3 gamma(2) + epsilon), STSP with weights one and two ( ratio 4/3) and ATSP with weights one and two ( ratio 3/2).
暂无评论