scientific article; zbMATH DE number 1839431

zbMath0999.68546MaRDI QIDQ4782696

Umesh V. Vazirani

Publication date: 2 December 2002

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2138/21380045

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Related Items (only showing first 100 items - show all)

New approximation results for resource replication problems ⋮ On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\) ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Theoretical complexity of grid cover problems used in radar applications ⋮ Models of greedy algorithms for graph problems ⋮ Online unit clustering and unit covering in higher dimensions ⋮ Approximability and exact resolution of the multidimensional binary vector assignment problem ⋮ On residual approximation in solution extension problems ⋮ Bin packing with divisible item sizes and rejection penalties ⋮ A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron ⋮ A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem ⋮ Approximations for constructing tree-form structures using specific material with fixed length ⋮ Games of fixed rank: a hierarchy of bimatrix games ⋮ Approximation algorithm and hardness results for defensive domination in graphs ⋮ A minimized-rule based approach for improving data currency ⋮ An approximation algorithm for solving the heterogeneous Chinese postman problem ⋮ Approximating the minimal sensor selection for supervisory control ⋮ Computing envy-freeable allocations with limited subsidies ⋮ Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions ⋮ Fast machine reassignment ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Towards the price of leasing online ⋮ Classes of linear programs solvable by coordinate-wise minimization ⋮ Enumerating disjunctions and conjunctions of paths and cuts in reliability theory ⋮ On the geometric set multicover problem ⋮ Unbalanced graph partitioning ⋮ Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing ⋮ On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs ⋮ Approximate min-max relations for odd cycles in planar graphs ⋮ Testing additive integrality gaps ⋮ Computational complexity and approximation for a generalization of the Euclidean problem on the Chebyshev center ⋮ The school bus problem on trees ⋮ A hard dial-a-ride problem that is easy on average ⋮ Reoptimization of constraint satisfaction problems with approximation resistant predicates ⋮ Approximation for vertex cover in \(\beta\)-conflict graphs ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem ⋮ Tree drawings revisited ⋮ Route-enabling graph orientation problems ⋮ A linear time approximation scheme for computing geometric maximum \(k\)-star ⋮ Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees ⋮ NP-hardness of some quadratic Euclidean 2-clustering problems ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Donation center location problem ⋮ Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications ⋮ The negative cycles polyhedron and hardness of checking some polyhedral properties ⋮ New geometry-inspired relaxations and algorithms for the metric Steiner tree problem ⋮ Tree metrics and edge-disjoint \(S\)-paths ⋮ On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field ⋮ Approximately fair cost allocation in metric traveling salesman games ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ Generating cut conjunctions in graphs and related problems ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Augmenting graphs to minimize the diameter ⋮ Online budgeted maximum coverage ⋮ A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing ⋮ Lagrangian relaxations for multiple network alignment ⋮ Constant-time local computation algorithms ⋮ The worm process for the Ising model is rapidly mixing ⋮ On the complexity and approximability of some Euclidean optimal summing problems ⋮ Approximation algorithm for partial positive influence problem in social network ⋮ On robust clusters of minimum cardinality in networks ⋮ Towards flexible demands in online leasing problems ⋮ Approximating the generalized minimum Manhattan network problem ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ Minimum-cost \(b\)-edge dominating sets on trees ⋮ 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem ⋮ A partition-based relaxation for Steiner trees ⋮ Greedy splitting algorithms for approximating multiway partition problems ⋮ Modularity-maximizing graph communities via mathematical programming ⋮ Dominating set of rectangles intersecting a straight line ⋮ Interdependent defense games with applications to internet security at the level of autonomous systems ⋮ Partial covering arrays: algorithms and asymptotics ⋮ Approximation algorithms for the load-balanced capacitated vehicle routing problem ⋮ Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ A robust APTAS for the classical bin packing problem ⋮ Convex relaxations of penalties for sparse correlated variables with bounded total variation ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ Approximation algorithms for multi-criteria traveling salesman problems ⋮ Path hitting in acyclic graphs ⋮ Disruption recovery at airports: ground holding, curfew restrictions and an approximation algorithm ⋮ Prototype selection for interpretable classification ⋮ Approximation algorithm for vertex cover with multiple covering constraints ⋮ A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem ⋮ Approximation algorithms for constructing required subgraphs using stock pieces of fixed length ⋮ A primal-dual algorithm for the minimum power partial cover problem ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs ⋮ Approximation algorithms for solving the heterogeneous Chinese postman problem ⋮ Economic lot-sizing problem with remanufacturing option: complexity and algorithms ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting ⋮ Optimized item selection to boost exploration for recommender systems ⋮ About Lagrangian methods in integer optimization ⋮ Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices ⋮ Error bounds for mixed integer linear optimization problems

This page was built for publication: