scientific article; zbMATH DE number 1559563
From MaRDI portal
Publication:4527015
Recommendations
- PCP characterizations of NP: towards a polynomially-small error-probability
- PCP characterizations of NP: toward a polynomially-small error-probability
- scientific article; zbMATH DE number 1559564
- A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
- Probabilistic checking of proofs
Cited in
(only showing first 100 items - show all)- 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
- 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
- Approximating covering integer programs with multiplicity constraints
- Algorithms for graphs with small octopus
- A neural network for the minimum set covering problem
- Interactive and probabilistic proof-checking
- Generalized submodular cover problems and applications
- Theoretical complexity of grid cover problems used in radar applications
- A new approximation algorithm for k-set cover problem
- The complexity of probabilistic lobbying
- Impact of locality on location aware unit disk graphs
- Decision trees for function evaluation: simultaneous optimization of worst and expected cost
- The advice complexity of a class of hard online problems
- Practical and efficient algorithms for the geometric hitting set problem
- Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results
- Greedy domination on biclique-free graphs
- On the approximability of Dodgson and Young elections
- Optimal covering designs: complexity results and new bounds
- The approximability of non-Boolean satisfiability problems and restricted integer programming
- Designing small keyboards is hard
- Improved approximation algorithms for capacitated facility location problems
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- The center location improvement problem under the Hamming distance
- Risk averse submodular utility maximization
- On the domination search number
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Algebraic testing and weight distributions of codes.
- PTAS for the minimum weighted dominating set in growth bounded graphs
- Improved approximation for spanning star forest in dense graphs
- Maximum subset intersection
- Approximation algorithms for the fault-tolerant facility placement problem
- Energy-efficient communication in multi-interface wireless networks
- Online budgeted maximum coverage
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Smooth and strong PCPs
- Algorithmic aspects of upper edge domination
- Approximation algorithm for stochastic set cover problem
- On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs
- On the induced matching problem in Hamiltonian bipartite graphs
- A local search 4/3-approximation algorithm for the minimum 3-path partition problem
- Succinct non-interactive arguments via linear interactive proofs
- Dual domination problems in graphs
- How to split the costs and charge the travellers sharing a ride? Aligning system's optimum with users' equilibrium
- Distributed distance domination in graphs with no \(K_{2,t}\)-minor
- Scalable algorithms for designing \(\mathrm{CO}_2\) capture and storage infrastructure
- 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
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- Network construction with subgraph connectivity constraints
- Erratum to: ``Internet shopping with price-sensitive discounts
- Restricted parameter range promise set cover problems are easy
- Pursuing a fast robber on a graph
- Paging with request sets
- Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
- Fast and frugal targeting with incentives
- Computing a small agreeable set of indivisible items
- 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
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- 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
- Tree-edges deletion problems with bounded diameter obstruction sets
- Tight approximation bounds for combinatorial frugal coverage algorithms
- Distinguishing pattern languages with membership examples
- Robust recoverable and two-stage selection problems
- Low-degree test with polynomially small error
- 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
- Hardness and inapproximability of convex recoloring problems
- On the \(k\)-edge-incident subgraph problem and its variants
- On the complexity of constructing minimum changeover cost arborescences
- 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
- Discrete sensor placement problems in distribution networks
- Improved low-degree testing and its applications
- Completeness in approximation classes beyond APX
- On influence, stable behavior, and the most influential individuals in networks: a game-theoretic approach
- Bulk-robust combinatorial optimization
- Approximation algorithms for covering/packing integer programs
- 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
- Multi-rooted greedy approximation of directed Steiner trees with applications
- Dominating problems in swapped networks
- Exact learning from an honest teacher that answers membership queries
- On the connectivity preserving minimum cut problem
- Tighter estimates for -nets for disks
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4527015)
