scientific article; zbMATH DE number 1559563
From MaRDI portal
zbMath0963.68175MaRDI QIDQ4527015
Publication date: 28 February 2001
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Tree-edges deletion problems with bounded diameter obstruction sets, Succinct non-interactive arguments via linear interactive proofs, Dual domination problems in graphs, Cube vs. Cube Low Degree Test., Dominating problems in swapped networks, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks, Distributed distance domination in graphs with no \(K_{2,t}\)-minor, Exact learning from an honest teacher that answers membership queries, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, On the connectivity preserving minimum cut problem, Scalable algorithms for designing \(\mathrm{CO}_2\) capture and storage infrastructure, Energy-Efficient Communication in Multi-interface Wireless Networks, Unnamed Item, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Tight approximation bounds for combinatorial frugal coverage algorithms, A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph, A polynomial-time approximation to a minimum dominating set in a graph, Online learning for min-max discrete problems, Approximating activation edge-cover and facility location problems, Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments, Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs, Distinguishing pattern languages with membership examples, Robust recoverable and two-stage selection problems, Line segment covering of cells in arrangements, Low-degree test with polynomially small error, Approximation algorithm for the stochastic prize-collecting set multicover problem, An improved approximation algorithm for the minimum 3-path partition problem, Approximation algorithms and hardness results for labeled connectivity problems, Approximation of the quadratic set covering problem, Unnamed Item, Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes, Hardness and inapproximability of convex recoloring problems, On the \(k\)-edge-incident subgraph problem and its variants, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees, On the complexity of constructing minimum changeover cost arborescences, The Constant Inapproximability of the Parameterized Dominating Set Problem, Fractional Set Cover in the Streaming Model., Tight Approximation Bounds for Greedy Frugal Coverage Algorithms, Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames, Admission control with advance reservations in simple networks, The minimum shift design problem, Polynomial-time approximation schemes for piercing and covering with applications in wireless networks, Network construction with subgraph connectivity constraints, Erratum to: ``Internet shopping with price-sensitive discounts, Restricted parameter range promise set cover problems are easy, Discrete sensor placement problems in distribution networks, Internet shopping optimization problem, Limitation on the Rate of Families of Locally Testable Codes, Composition of Low-Error 2-Query PCPs Using Decodable PCPs, Some Recent Results on Local Testing of Sparse Linear Codes, Pursuing a fast robber on a graph, Paging with request sets, On Partial Covers, Reducts and Decision Rules, Unnamed Item, Completeness in approximation classes beyond APX, Reoptimization of Weighted Graph and Covering Problems, Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs, Cost-effective designs of fault-tolerant access networks in communication systems, Unnamed Item, Smooth and strong PCPs, On influence, stable behavior, and the most influential individuals in networks: a game-theoretic approach, Algorithmic aspects of upper edge domination, Bulk-robust combinatorial optimization, Approximation algorithm for stochastic set cover problem, Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs, Recent Developments in Algorithmic Teaching, On the Discrete Unit Disk Cover Problem, Clustering with Internal Connectedness, Fast and frugal targeting with incentives, Three-Player Entangled XOR Games are NP-Hard to Approximate, Erratum: Three-Player Entangled XOR Games are NP-hard to Approximate, On the Approximability of Some Haplotyping Problems, On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs, On the induced matching problem in Hamiltonian bipartite graphs, From Local to Robust Testing via Agreement Testing, A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, Near-Optimal Dominating Sets via Random Sampling, Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks, Self-correctors for Cryptographic Modules, Computing a small agreeable set of indivisible items, Algorithms for a network design problem with crossing supermodular demands, Designing Hypergraph Layouts to GMPLS Routing Strategies, Set cover problems with small neighborhood covers, Parameterized analysis of the online priority and node-weighted Steiner tree problems, On interval and circular-arc covering problems, Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames, A local search 4/3-approximation algorithm for the minimum 3-path partition problem, Approximation algorithms for covering/packing integer programs, An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries, The minimum-entropy set cover problem, A greedy approximation algorithm for the group Steiner problem, An improved approximation algorithm for vertex cover with hard capacities, Hardness of approximation for knapsack problems, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, Some results on more flexible versions of Graph Motif, On connected dominating sets of restricted diameter, Geometric dominating-set and set-cover via local-search, Distributed Graph Algorithms and their Complexity: An Introduction, Covering Points by Unit Disks of Fixed Location, Randomized greedy algorithms for finding smallk-dominating sets of regular graphs, The Optimal Design of Low-Latency Virtual Backbones, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, On a minimum linear classification problem, The Minimum Substring Cover Problem, Parameterized approximation algorithms for some location problems in graphs, Unnamed Item, An approximation algorithm for the partial vertex cover problem in hypergraphs, Finding large degree-anonymous subgraphs is hard, Minimum membership covering and hitting, Order Scheduling Models: Hardness and Algorithms, Hull and geodetic numbers for some classes of oriented graphs, Lowering eccentricity of a tree by node upgrading, Unnamed Item, Unnamed Item, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Robust locally testable codes and products of codes, Unnamed Item, Unnamed Item, Tighter estimates for \(\epsilon\)-nets for disks, Algebraic testing and weight distributions of codes., Theoretical complexity of grid cover problems used in radar applications, Quantum information and the PCP theorem, Optimal cost sharing for capacitated facility location games, Integrality gaps for strengthened linear relaxations of capacitated facility location, A new approximation algorithm for \(k\)-set cover problem, Structural identifiability in low-rank matrix factorization, The complexity of probabilistic lobbying, New primal-dual algorithms for Steiner tree problems, Impact of locality on location aware unit disk graphs, Distributed minimum dominating set approximations in restricted families of graphs, Testing juntas, Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks, Improved results on geometric hitting set problems, Hardness of \(k\)-vertex-connected subgraph augmentation problem, Decision trees for function evaluation: simultaneous optimization of worst and expected cost, PTAS for the minimum weighted dominating set in growth bounded graphs, The \(l\)-diversity problem: tractability and approximability, Statistical mechanics of the minimum dominating set problem, Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs, The advice complexity of a class of hard online problems, Data reductions and combinatorial bounds for improved approximation algorithms, On the approximation ability of evolutionary optimization with application to minimum set cover, Approximating covering integer programs with multiplicity constraints, Improved approximation for spanning star forest in dense graphs, Maximum subset intersection, Approximation algorithms for the fault-tolerant facility placement problem, On the approximability of covering points by lines and related problems, Uniform unweighted set cover: the power of non-oblivious local search, Energy-efficient communication in multi-interface wireless networks, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Improved approximation for guarding simple galleries from the perimeter, Approximating some network design problems with node costs, Practical and efficient algorithms for the geometric hitting set problem, GMPLS label space minimization through hypergraph layouts, Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results, Derandomized parallel repetition via structured PCPs, Algorithms for graphs with small octopus, PCP characterizations of NP: toward a polynomially-small error-probability, A survey on the structure of approximation classes, Guard games on graphs: keep the intruder out!, How to guard a graph?, Augmenting edge-connectivity between vertex subsets, Computing on binary strings, Inapproximability of dominating set on power law graphs, Tight approximation algorithm for connectivity augmentation problems, On finding the longest antisymmetric path in directed acyclic graphs, Greedy domination on biclique-free graphs, Correcting gene tree by removal and modification: tractability and approximability, Parameterized lower bound and inapproximability of polylogarithmic string barcoding, Online budgeted maximum coverage, Inapproximability results for graph convexity parameters, Shorter arithmetization of nondeterministic computations, On the complexity of the flow coloring problem, Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs, Directed hypergraphs: introduction and fundamental algorithms -- a survey, Separating sets of strings by finding matching patterns is almost always hard, On robust clusters of minimum cardinality in networks, The minimum substring cover problem, Commitment under uncertainty: Two-stage stochastic matching problems, Limits of local search: quality and efficiency, Complexity issues in vertex-colored graph pattern matching, On the approximability of Dodgson and Young elections, Optimal covering designs: complexity results and new bounds, On the complexity of fixed parameter clique and dominating set, Approximating minimum power covers of intersecting families and directed edge-connectivity problems, Teaching randomized learners with feedback, The approximability of non-Boolean satisfiability problems and restricted integer programming, Designing small keyboards is hard, A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership, Improved approximation algorithms for capacitated facility location problems, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, New results on optimizing rooted triplets consistency, On regression-based stopping times, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, Optimally learning social networks with activations and suppressions, Domination in graphs with bounded propagation: Algorithms, formulations and hardness results, The center location improvement problem under the Hamming distance, Risk averse submodular utility maximization, Hitting sets online and unique-MAX coloring, A randomised approximation algorithm for the hitting set problem, Approximating the minimum independent dominating set in perturbed graphs, On the domination search number, A note on two source location problems, Connected domination of regular graphs, A new approach for approximating node deletion problems, On the hardness of approximating label-cover, Improved approximability and non-approximability results for graph diameter decreasing problems, On two restricted ancestors tree problems, A neural network for the minimum set covering problem, Interactive and probabilistic proof-checking, The labeled perfect matching in bipartite graphs, Vertex covering by paths on trees with its applications in machine translation, Approximating the weight of shallow Steiner trees, Generalized submodular cover problems and applications, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Iterative Dutch combinatorial auctions, Approximating cost-based abduction is NP-hard, Multi-rooted greedy approximation of directed Steiner trees with applications
