2498:
225:. This approach aims to overcome the limitations of both traditional approaches by having stronger guarantees on the solution quality compared to traditional approximations while still having efficient running times as in FPT algorithms. An overview of the research area studying parameterized approximation algorithms can be found in the survey of Marx and the more recent survey by Feldmann et al.
1679:. For the more general version with vertex capacities, an EPAS exists for the parameterization by k and the doubling dimension, but not when using k and the highway dimension as the parameter. Regarding the pathwidth, k-Center admits an EPAS even for the more general
52:-approximation, in polynomial time. On the other hand, parameterized algorithms are designed to find exact solutions to problems, but with the constraint that the running time of the algorithm is polynomial in the input size and a function of a specific parameter
1161:
2219:. However the guaranteed approximate kernel might be of exponential size (or worse) in the input parameter. Hence it becomes interesting to find problems that admit polynomial sized approximate kernels. Furthermore, a
2358:), but a PSAKS exists. When parameterizing Steiner Tree by the number of non-terminals in the optimum solution, the problem is W-hard (and thus admits no exact kernel at all, unless FPT=W), but still admits a PSAKS.
56:. The parameter describes some property of the input and is small in typical applications. The problem is said to be fixed-parameter tractable (FPT) if there is an algorithm that can find the optimum solution in
2214:
As for regular (non-approximate) kernels, a problem admits an α-approximate kernelization algorithm if and only if it has a parameterized α-approximation algorithm. The proof of this fact is very similar to
2356:
2322:
1037:
467:
2797:
Feldmann, Andreas Emil; Lampis, Michael (2024). "Parameterized
Algorithms for Steiner Forest in Bounded Width Graphs". In Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (eds.).
791:
332:
900:
1221:
671:
1852:
1484:
1438:
2285:
754:
585:
381:
1641:
1303:
1076:
960:
831:
728:
617:
413:
512:
2259:
1271:
1995:
1532:
1351:
552:
532:
287:
190:
102:
3027:
Cohen-Addad, Vincent; Gupta, Anupam; Kumar, Amit; Lee, Euiwoong; Li, Jason (2019). Baier, Christel; Chatzigiannakis, Ioannis; Flocchini, Paola; Leonardi, Stefano (eds.).
2916:
Chitnis, Rajesh; Hajiaghayi, MohammadTaghi; Kortsarz, Guy (2013). "Fixed-Parameter and
Approximation Algorithms: A New Look". In Gutin, Gregory; Szeider, Stefan (eds.).
1902:
2195:
2166:
2130:
2105:
2080:
2055:
1748:
140:
A parameterized approximation algorithm aims to find a balance between these two approaches by finding approximate solutions in FPT time: the algorithm computes an
1947:
219:
131:
1780:
678:
1081:
2290:
For example, while the
Connected Vertex Cover problem is FPT parameterized by the solution size, it does not admit a (regular) polynomial sized kernel (unless
2324:), but a PSAKS exists. Similarly, the Steiner Tree problem is FPT parameterized by the number of terminals, does not admit a polynomial sized kernel (unless
3078:
Kolliopoulos, Stavros G.; Rao, Satish (1999). "A Nearly Linear-Time
Approximation Scheme for the Euclidean k-median Problem". In Nešetřil, Jaroslav (ed.).
34:
in polynomial time in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional
2205:
in polynomial time. This notion was introduced by
Lokshtanov et al., but there are other related notions in the literature such as Turing kernels and
477:. This then circumvents the lower bounds in terms of polynomial-time approximation and fixed-parameter tractability. A PAS is similar in spirit to a
1542:. Matching parameterized approximation algorithms exist, but it is not known whether matching approximations can be computed in polynomial time.
3791:
3734:
3679:
3587:
3540:
3429:
3228:
3183:
3138:
3095:
3054:
2943:
2892:
478:
2518:"Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis"
3921:
3916:
2327:
2293:
2024:
problem in order to remove "easy parts" and reveal the NP-hard core of the instance. A kernelization algorithm takes an instance
1711:
1644:
1545:
Clustering is often considered in settings of low dimensional data, and thus a practically relevant parameterization is by the
1224:
294:
2367:
794:
3515:"Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension"
965:
2372:
418:
3082:. Lecture Notes in Computer Science. Vol. 1643. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 378–389.
1859:
1539:
1358:
759:
300:
836:
534:
is assumed to be arbitrary but constant in order for the PAS to run in FPT time. If this assumption is unsatisfying,
2799:
51st
International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8–12, 2024, Tallinn, Estonia
2740:
Dvořák, Pavel; Feldmann, Andreas E.; Knop, Dušan; Masařík, Tomáš; Toufar, Tomáš; Veselý, Pavel (January 1, 2021).
3770:
3564:. Lecture Notes in Computer Science. Vol. 13453. Cham: Springer International Publishing. pp. 215–229.
2920:. Lecture Notes in Computer Science. Vol. 8246. Cham: Springer International Publishing. pp. 110–122.
1178:
2017:
1574:
919:
622:
350:
339:
39:
3513:
Becker, Amariah; Klein, Philip N.; Saulpic, David (2018). Azar, Yossi; Bast, Hannah; Herman, Grzegorz (eds.).
2143:
is a variation of this technique that is used in parameterized approximation algorithms. It returns a kernel
1789:
1751:
914:
is FPT parameterized by the number of terminals. However, for the "dual" parameter consisting of the number
35:
2568:
1917:
1443:
1397:
3560:-Center: Distinguishing Doubling and Highway Dimension". In Bekos, Michael A.; Kaufmann, Michael (eds.).
1039:
time. The more general
Steiner Forest problem is NP-hard on graphs of treewidth 3. However, on graphs of
44:
In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor
1595:
a 2-approximation can be computed in polynomial time. However, when parameterizing by either the number
2264:
1171:
It is known that the
Strongly Connected Steiner Subgraph problem is W-hard parameterized by the number
733:
564:
360:
3867:
3604:
3310:
2699:
1614:
1276:
1049:
933:
804:
701:
590:
386:
1696:
911:
488:
234:
31:
2238:
3911:
1230:
1952:
1489:
1308:
537:
517:
244:
147:
59:
3844:
3797:
3740:
3712:
3685:
3616:
3565:
3495:
3469:
3435:
3390:
3364:
3291:
3265:
3234:
3189:
3144:
3116:
3060:
3006:
2980:
2949:
2921:
2898:
2802:
2801:. LIPIcs. Vol. 297. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 61:1–61:20.
2779:
2753:
2631:
2529:
2466:
1384:
1865:
3815:
Hermelin, Danny; Kratsch, Stefan; Sołtys, Karolina; Wahlström, Magnus; Wu, Xi (March 1, 2015).
2383:
Ariel Kulik. Two-variable
Recurrence Relations with Application to Parameterized Approximations
3887:
3836:
3787:
3730:
3675:
3634:
3583:
3536:
3487:
3425:
3382:
3330:
3283:
3224:
3179:
3134:
3091:
3050:
2998:
2939:
2888:
2853:
2771:
2719:
2649:
2604:
2549:
2486:
1676:
1660:
1608:
1570:
2742:"Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices"
2668:
3879:
3828:
3779:
3722:
3665:
3626:
3575:
3526:
3479:
3417:
3374:
3322:
3275:
3216:
3171:
3126:
3083:
3040:
2990:
2931:
2880:
2845:
2812:
2763:
2711:
2680:
2641:
2594:
2584:
2539:
2476:
2435:
1604:
1377:
2229:-approximate kernelization algorithm that computes a polynomial-sized kernel and for which
1721:
2502:
2497:
1923:
1589:
1554:
1156:{\displaystyle 2^{O({\frac {t^{2}}{\varepsilon }}\log {\frac {t}{\varepsilon }})}n^{O(1)}}
195:
107:
3711:. STOC 2018. New York, NY, USA: Association for Computing Machinery. pp. 1283–1296.
1757:
3111:
Cohen-Addad, Vincent (2018). "A Fast
Approximation Scheme for Low-Dimensional k-Means".
2501: This article incorporates text from this source, which is available under the
2175:
2146:
2110:
2085:
2060:
2035:
3863:
3778:. STOC 2017. New York, NY, USA: Association for Computing Machinery. pp. 224–237.
1855:
1700:
1656:
1600:
1566:
923:
3765:
Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket (June 19, 2017).
3353:"Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs"
3311:"Polynomial time approximation schemes for clustering in low highway dimension graphs"
3215:. STOC '11. New York, NY, USA: Association for Computing Machinery. pp. 569–578.
2879:. STOC '03. New York, NY, USA: Association for Computing Machinery. pp. 585–594.
2589:
2573:"Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems"
2572:
233:
The full potential of parameterized approximation algorithms is utilized when a given
3905:
3848:
3295:
3064:
3028:
3010:
2216:
2013:
692:
3801:
3653:
3514:
3394:
3168:
Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07
3148:
3744:
3689:
3664:. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:20.
3499:
3414:
Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88
3238:
3193:
3039:. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 42:1–42:14.
2953:
2902:
2783:
2393:
Vincent Cohen-Added: On the Parameterized Complexity of Various Clustering Problems
2378:
Karthik C. S.: Recent Hardness of Approximation results in Parameterized Complexity
1684:
1648:
1550:
485:. Since the degree of the polynomial in the runtime of a PAS depends on a function
3439:
3033:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
3579:
3525:. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 8:1–8:15.
3252:
Cohen-Addad, Vincent; Feldmann, Andreas Emil; Saulpic, David (October 31, 2021).
3115:. Proceedings. Society for Industrial and Applied Mathematics. pp. 430–440.
3045:
2935:
2817:
1557:, the k-Median and k-Means problems admit an EPAS parameterized by the dimension
3670:
2969:"Parameterized Approximation Algorithms for Bidirected Steiner Network Problems"
2741:
2623:
2455:"A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms"
2373:
Tuukka Korhonen: Single-Exponential Time 2-Approximation Algorithm for Treewidth
2021:
1671:
with the doubling dimension an EPAS exists, and the same is true when combining
28:
3883:
3603:
Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis Th. (July 15, 2019).
3483:
3458:"The Parameterized Hardness of the k-Center Problem in Transportation Networks"
3326:
3130:
3113:
Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
2833:
2622:
Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (April 25, 2022).
2453:
Feldmann, Andreas Emil; Karthik C. S; Lee, Euiwoong; Manurangsi, Pasin (2020).
3832:
3630:
3531:
3378:
2715:
2402:
2397:
2392:
2387:
2382:
2377:
3891:
3840:
3638:
3491:
3457:
3386:
3334:
3287:
3087:
3002:
2967:
Chitnis, Rajesh; Feldmann, Andreas Emil; Manurangsi, Pasin (April 19, 2021).
2857:
2775:
2723:
2653:
2608:
2553:
2490:
2403:
Andreas Emil Feldmann. Approximate Kernelization Schemes for Steiner Networks
3816:
3783:
3726:
3416:. New York, NY, USA: Association for Computing Machinery. pp. 434–444.
3352:
3220:
3175:
2439:
2398:
Fahad Panolan. Parameterized Approximation for Independent Set of Rectangles
1680:
1664:
1546:
1040:
24:
3254:"Near-linear Time Approximation Schemes for Clustering in Doubling Metrics"
2877:
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing
2684:
3772:
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
3766:
3709:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
3704:
3213:
Proceedings of the forty-third annual ACM symposium on Theory of computing
3208:
3170:. New York, NY, USA: Association for Computing Machinery. pp. 11–18.
3163:
2884:
3605:"Structural parameters, tight bounds, and approximation for (k,r)-center"
3703:
S., Karthik C.; Laekhanukit, Bundit; Manurangsi, Pasin (June 20, 2018).
3421:
2872:
2423:
1565:. The former was generalized to an EPAS for the parameterization by the
2767:
2645:
2599:
3658:
9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
3409:
3162:
Feldman, Dan; Monemizadeh, Morteza; Sohler, Christian (June 6, 2007).
2849:
2544:
2517:
2481:
2454:
3868:"Parameterized approximation via fidelity preserving transformations"
2368:
Daniel Lokshtanov: A Parameterized Approximation Scheme for k-Min Cut
3279:
2994:
2834:"Parameterized Complexity of Arc-Weighted Directed Steiner Problems"
3717:
3654:"ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network"
3621:
3570:
3474:
3369:
3270:
3121:
2985:
2807:
2758:
2636:
2534:
2471:
918:
of non-terminals contained in the optimum solution, the problem is
3253:
2968:
2926:
1718:
vertices with maximum number of edges. It is not hard to obtain a
289:
time, while in contrast the problem neither has a polynomial-time
3705:"On the parameterized complexity of approximating dominating set"
801:
of required components. However an EPAS exists, which computes a
2832:
Guo, Jiong; Niedermeier, Rolf; Suchý, Ondřej (January 1, 2011).
2567:
G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael;
2700:"The Steiner tree problem on graphs: Inapproximability results"
1782:
in the given input graph, since the maximum number of edges on
3652:
Dinur, Irit; Manurangsi, Pasin (2018). Karlin, Anna R. (ed.).
927:
346:
3817:"A Completeness Theory for Polynomial (Turing) Kernelization"
3660:. Leibniz International Proceedings in Informatics (LIPIcs).
3521:. Leibniz International Proceedings in Informatics (LIPIcs).
3035:. Leibniz International Proceedings in Informatics (LIPIcs).
2351:{\displaystyle {\textsf {NP}}\subseteq {\textsf {coNP/poly}}}
2317:{\displaystyle {\textsf {NP}}\subseteq {\textsf {coNP/poly}}}
1904:-approximation can be computed in FPT time parameterized by
3611:. Combinatorial Optimization: between Practice and Theory.
3309:
Feldmann, Andreas Emil; Saulpic, David (December 1, 2021).
3209:"A unified framework for approximating and clustering data"
3556:
Feldmann, Andreas Emil; Vu, Tung Anh (2022). "Generalized
2698:
Chlebík, Miroslav; Chlebíková, Janka (October 31, 2008).
2579:. CATS'03, Computing: the Australasian Theory Symposium.
2221:
polynomial-sized approximate kernelization scheme (PSAKS)
2624:"A Parameterized Approximation Scheme for Min $ k$ -Cut"
3519:
26th Annual European Symposium on Algorithms (ESA 2018)
2424:"Parameterized Complexity and Approximation Algorithms"
679:
efficient polynomial-time approximation scheme (EPTAS).
3862:
Fellows, Michael R.; Kulik, Ariel; Rosamond, Frances;
3164:"A PTAS for k-means clustering based on weak coresets"
1647:. Furthermore, the k-Center problem is W-hard even on
3456:
Feldmann, Andreas Emil; Marx, Dániel (July 1, 2020).
2330:
2296:
2267:
2241:
2178:
2149:
2113:
2088:
2063:
2038:
1955:
1926:
1868:
1792:
1760:
1724:
1617:
1492:
1446:
1400:
1311:
1279:
1233:
1181:
1084:
1052:
1032:{\displaystyle 2^{O(k^{2}/\varepsilon ^{4})}n^{O(1)}}
968:
936:
839:
807:
762:
736:
704:
625:
593:
567:
540:
520:
491:
421:
389:
363:
303:
247:
198:
150:
110:
62:
2871:
Halperin, Eran; Krauthgamer, Robert (June 9, 2003).
1651:
when simultaneously parameterizing it by the number
462:{\displaystyle f(k,\varepsilon )n^{g(\varepsilon )}}
3029:"Tight FPT Approximations for k-Median and k-Means"
1376:For the well-studied metric clustering problems of
1273:time. Furthermore, this is best possible, since no
2350:
2316:
2279:
2253:
2189:
2160:
2124:
2099:
2074:
2049:
1989:
1941:
1896:
1846:
1774:
1742:
1635:
1526:
1478:
1432:
1345:
1297:
1265:
1223:-approximation in polynomial time (under standard
1215:
1155:
1070:
1031:
954:
894:
825:
785:
748:
722:
665:
611:
579:
546:
526:
506:
461:
407:
375:
326:
281:
213:
184:
125:
96:
1809:
1796:
3408:Feder, Tomás; Greene, Daniel (January 1, 1988).
3207:Feldman, Dan; Langberg, Michael (June 6, 2011).
2577:Electronic Notes in Theoretical Computer Science
2136:, and the algorithm runs in polynomial time. An
2132:is bounded as a function of the input parameter
1643:-approximation algorithm exists, under standard
1227:). However a 2-approximation can be computed in
797:. It is also W-hard parameterized by the number
786:{\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}
334:), nor an FPT algorithm for the given parameter
327:{\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}
3410:"Optimal algorithms for approximate clustering"
895:{\displaystyle (k/\varepsilon )^{O(k)}n^{O(1)}}
554:is treated as a parameter as well to obtain an
1486:-approximation for k-Means can be computed in
1573:parameter, only an approximation scheme with
8:
3562:Graph-Theoretic Concepts in Computer Science
481:but additionally exploits a given parameter
221:is a function independent of the input size
133:is a function independent of the input size
48:away from the optimal solution, known as an
2706:. Algorithmic Aspects of Global Computing.
1714:), where the task is to find a subgraph on
479:polynomial-time approximation scheme (PTAS)
27:that aims to find approximate solutions to
1216:{\displaystyle O(\log ^{2-\varepsilon }n)}
3716:
3669:
3620:
3569:
3530:
3473:
3368:
3269:
3120:
3044:
2984:
2925:
2816:
2806:
2757:
2635:
2598:
2588:
2543:
2533:
2480:
2470:
2343:
2342:
2341:
2333:
2332:
2331:
2329:
2309:
2308:
2307:
2299:
2298:
2297:
2295:
2266:
2240:
2177:
2148:
2112:
2087:
2062:
2037:
1972:
1954:
1925:
1873:
1867:
1836:
1808:
1795:
1793:
1791:
1764:
1759:
1723:
1616:
1509:
1491:
1459:
1445:
1413:
1399:
1328:
1310:
1278:
1248:
1238:
1232:
1192:
1180:
1175:of terminals, and also does not admit an
1138:
1119:
1102:
1096:
1089:
1083:
1051:
1014:
999:
990:
984:
973:
967:
935:
877:
858:
846:
838:
806:
774:
773:
764:
763:
761:
735:
703:
666:{\displaystyle f(k,\varepsilon )n^{O(1)}}
648:
624:
592:
566:
559:parameterized approximation scheme (EPAS)
539:
519:
490:
444:
420:
388:
362:
315:
314:
305:
304:
302:
264:
246:
197:
167:
149:
109:
79:
61:
3351:Feldmann, Andreas Emil (March 1, 2019).
2571:; Rosamund, Frances A. (April 1, 2003).
930:. However, there is an EPAS computing a
355:parameterized approximation scheme (PAS)
3872:Journal of Computer and System Sciences
3315:Journal of Computer and System Sciences
2414:
2667:Dreyfus, S. E.; Wagner, R. A. (1971).
1847:{\displaystyle {k \choose 2}=k(k-1)/2}
922:(due to a folklore reduction from the
778:
775:
765:
319:
316:
306:
3760:
3758:
3756:
3754:
3451:
3449:
3346:
3344:
3022:
3020:
2362:Talks on parameterized approximations
2201:-approximation to the input instance
293:-approximation algorithm (under some
21:parameterized approximation algorithm
7:
2838:SIAM Journal on Discrete Mathematics
2746:SIAM Journal on Discrete Mathematics
2735:
2733:
2141:-approximate kernelization algorithm
1710:-Subgraph problem (which is a 2-ary
1561:, and also an EPAS parameterized by
1479:{\displaystyle (1+8/e-\varepsilon )}
1433:{\displaystyle (1+2/e-\varepsilon )}
926:). Steiner Tree is also known to be
345:For example, some problems that are
241:-approximation algorithm running in
2918:Parameterized and Exact Computation
2873:"Polylogarithmic inapproximability"
1440:-approximation for k-Median and no
1167:Strongly-connected Steiner subgraph
1800:
1305:-approximation can be computed in
677:. This is similar in spirit to an
415:-approximation can be computed in
14:
2280:{\displaystyle \varepsilon >0}
2020:to pre-process an instance of an
1750:-approximation by just picking a
749:{\displaystyle \varepsilon >0}
730:-approximation algorithm for any
580:{\displaystyle \varepsilon >0}
376:{\displaystyle \varepsilon >0}
2496:
2388:Meirav Zehavi. FPT Approximation
1636:{\displaystyle (2-\varepsilon )}
1394:of centers, it is known that no
1298:{\displaystyle (2-\varepsilon )}
1071:{\displaystyle (1+\varepsilon )}
955:{\displaystyle (1+\varepsilon )}
826:{\displaystyle (1+\varepsilon )}
723:{\displaystyle (2-\varepsilon )}
612:{\displaystyle (1+\varepsilon )}
408:{\displaystyle (1+\varepsilon )}
2669:"The steiner problem in graphs"
1712:Constraint Satisfaction problem
698:problem has no polynomial-time
507:{\displaystyle g(\varepsilon )}
229:Obtainable approximation ratios
2973:ACM Transactions on Algorithms
2254:{\displaystyle 1+\varepsilon }
1982:
1976:
1965:
1959:
1936:
1930:
1889:
1883:
1833:
1821:
1737:
1725:
1630:
1618:
1519:
1513:
1502:
1496:
1473:
1447:
1427:
1401:
1338:
1332:
1321:
1315:
1292:
1280:
1258:
1252:
1210:
1185:
1148:
1142:
1129:
1093:
1065:
1053:
1024:
1018:
1005:
977:
949:
937:
887:
881:
868:
862:
855:
840:
820:
808:
795:small set expansion hypothesis
717:
705:
658:
652:
641:
629:
606:
594:
501:
495:
454:
448:
437:
425:
402:
390:
274:
268:
257:
251:
208:
202:
177:
171:
160:
154:
120:
114:
89:
83:
72:
66:
1:
2590:10.1016/S1571-0661(04)81014-4
2032:, and returns a new instance
1266:{\displaystyle 3^{k}n^{O(1)}}
40:fixed-parameter tractability.
3609:Discrete Applied Mathematics
3580:10.1007/978-3-031-15914-5_16
3046:10.4230/LIPIcs.ICALP.2019.42
2936:10.1007/978-3-319-03898-8_11
2818:10.4230/LIPICS.ICALP.2024.61
2704:Theoretical Computer Science
2018:fixed-parameter tractability
1990:{\displaystyle f(k)n^{O(1)}}
1920:it is W-hard to compute any
1603:(in fact the dimension of a
1527:{\displaystyle f(k)n^{O(1)}}
1390:parameterized by the number
1346:{\displaystyle f(k)n^{O(1)}}
547:{\displaystyle \varepsilon }
527:{\displaystyle \varepsilon }
282:{\displaystyle f(k)n^{O(1)}}
185:{\displaystyle f(k)n^{O(1)}}
97:{\displaystyle f(k)n^{O(1)}}
3671:10.4230/LIPIcs.ITCS.2018.36
2217:the one for regular kernels
1786:vertices is always at most
3938:
3884:10.1016/j.jcss.2017.11.001
3484:10.1007/s00453-020-00683-w
3327:10.1016/j.jcss.2021.06.002
3131:10.1137/1.9781611975031.29
2516:Manurangsi, Pasin (2018).
1897:{\displaystyle k^{1-o(1)}}
1667:. However, when combining
1577:runtime is known to date.
1569:. For the loosely related
3833:10.1007/s00453-014-9910-8
3631:10.1016/j.dam.2018.11.002
3532:10.4230/LIPIcs.ESA.2018.8
3379:10.1007/s00453-018-0455-0
2716:10.1016/j.tcs.2008.06.046
2628:SIAM Journal on Computing
2211:-fidelity kernelization.
2197:can be converted into an
2009:Approximate kernelization
1858:optimal, since under Gap-
3922:Parameterized complexity
3917:Approximation algorithms
3088:10.1007/3-540-48481-7_33
1683:parameter, and also for
469:time for some functions
36:approximation algorithms
3784:10.1145/3055399.3055456
3727:10.1145/3188745.3188896
3221:10.1145/1993636.1993712
3176:10.1145/1247069.1247072
2016:is a technique used in
1997:time for any functions
673:time for some function
2685:10.1002/net.3230010302
2352:
2318:
2281:
2255:
2191:
2162:
2126:
2101:
2082:such that the size of
2076:
2051:
1991:
1943:
1918:Dominating set problem
1898:
1848:
1776:
1744:
1645:complexity assumptions
1637:
1534:time for any function
1528:
1480:
1434:
1353:time for any function
1347:
1299:
1267:
1225:complexity assumptions
1217:
1157:
1072:
1046:an EPAS can compute a
1033:
956:
924:Dominating Set problem
896:
827:
787:
750:
724:
667:
613:
581:
548:
528:
508:
463:
409:
377:
338:(i.e., it is at least
328:
283:
215:
186:
127:
98:
3767:"Lossy kernelization"
2885:10.1145/780542.780628
2440:10.1093/comjnl/bxm048
2422:Marx, Daniel (2008).
2353:
2319:
2282:
2256:
2192:
2163:
2127:
2102:
2077:
2052:
1992:
1944:
1899:
1849:
1777:
1745:
1743:{\displaystyle (k-1)}
1638:
1529:
1481:
1435:
1348:
1300:
1268:
1218:
1158:
1073:
1034:
957:
897:
828:
788:
751:
725:
668:
614:
582:
549:
529:
509:
464:
410:
378:
329:
295:complexity assumption
284:
237:is shown to admit an
216:
187:
128:
99:
32:optimization problems
3080:Algorithms - ESA' 99
2428:The Computer Journal
2328:
2294:
2265:
2239:
2176:
2147:
2111:
2086:
2061:
2036:
1953:
1942:{\displaystyle g(k)}
1924:
1866:
1790:
1758:
1722:
1615:
1490:
1444:
1398:
1309:
1277:
1231:
1179:
1082:
1050:
966:
934:
912:Steiner Tree problem
837:
805:
760:
734:
702:
623:
591:
565:
538:
518:
489:
419:
387:
361:
301:
245:
235:optimization problem
214:{\displaystyle f(k)}
196:
148:
126:{\displaystyle f(k)}
108:
60:
3422:10.1145/62212.62255
1775:{\displaystyle k/2}
1611:, no parameterized
3258:Journal of the ACM
2768:10.1137/18M1209489
2646:10.1137/20M1383197
2348:
2314:
2277:
2251:
2190:{\displaystyle I'}
2187:
2172:-approximation in
2161:{\displaystyle I'}
2158:
2125:{\displaystyle k'}
2122:
2100:{\displaystyle I'}
2097:
2075:{\displaystyle k'}
2072:
2050:{\displaystyle I'}
2047:
1987:
1949:-approximation in
1939:
1894:
1844:
1772:
1740:
1657:doubling dimension
1633:
1601:doubling dimension
1567:doubling dimension
1549:of the underlying
1524:
1476:
1430:
1343:
1295:
1263:
1213:
1153:
1078:-approximation in
1068:
1029:
962:-approximation in
952:
892:
833:-approximation in
823:
783:
746:
720:
663:
619:-approximation in
609:
577:
544:
524:
504:
459:
405:
373:
324:
279:
211:
182:
144:-approximation in
123:
94:
3793:978-1-4503-4528-6
3736:978-1-4503-5559-9
3681:978-3-95977-060-6
3589:978-3-031-15914-5
3542:978-3-95977-081-1
3431:978-0-89791-264-8
3264:(6): 44:1–44:34.
3230:978-1-4503-0691-1
3185:978-1-59593-705-6
3140:978-1-61197-503-1
3097:978-3-540-66251-8
3056:978-3-95977-109-2
2979:(2): 12:1–12:68.
2945:978-3-319-03898-8
2894:978-1-58113-674-6
2850:10.1137/100794560
2545:10.3390/a11010010
2482:10.3390/a13060146
2345:
2335:
2311:
2301:
1807:
1677:highway dimension
1661:highway dimension
1609:highway dimension
1571:highway dimension
1127:
1111:
16:Type of algorithm
3929:
3896:
3895:
3859:
3853:
3852:
3812:
3806:
3805:
3777:
3762:
3749:
3748:
3720:
3700:
3694:
3693:
3673:
3649:
3643:
3642:
3624:
3600:
3594:
3593:
3573:
3559:
3553:
3547:
3546:
3534:
3510:
3504:
3503:
3477:
3468:(7): 1989–2005.
3453:
3444:
3443:
3405:
3399:
3398:
3372:
3363:(3): 1031–1052.
3348:
3339:
3338:
3306:
3300:
3299:
3273:
3249:
3243:
3242:
3204:
3198:
3197:
3159:
3153:
3152:
3124:
3108:
3102:
3101:
3075:
3069:
3068:
3048:
3024:
3015:
3014:
2988:
2964:
2958:
2957:
2929:
2913:
2907:
2906:
2868:
2862:
2861:
2829:
2823:
2822:
2820:
2810:
2794:
2788:
2787:
2761:
2737:
2728:
2727:
2695:
2689:
2688:
2664:
2658:
2657:
2639:
2619:
2613:
2612:
2602:
2592:
2564:
2558:
2557:
2547:
2537:
2513:
2507:
2500:
2494:
2484:
2474:
2450:
2444:
2443:
2419:
2357:
2355:
2354:
2349:
2347:
2346:
2337:
2336:
2323:
2321:
2320:
2315:
2313:
2312:
2303:
2302:
2286:
2284:
2283:
2278:
2260:
2258:
2257:
2252:
2233:
2227:
2209:
2204:
2200:
2196:
2194:
2193:
2188:
2186:
2171:
2167:
2165:
2164:
2159:
2157:
2140:
2135:
2131:
2129:
2128:
2123:
2121:
2106:
2104:
2103:
2098:
2096:
2081:
2079:
2078:
2073:
2071:
2056:
2054:
2053:
2048:
2046:
2031:
2028:and a parameter
2027:
2004:
2000:
1996:
1994:
1993:
1988:
1986:
1985:
1948:
1946:
1945:
1940:
1907:
1903:
1901:
1900:
1895:
1893:
1892:
1853:
1851:
1850:
1845:
1840:
1814:
1813:
1812:
1799:
1785:
1781:
1779:
1778:
1773:
1768:
1749:
1747:
1746:
1741:
1717:
1691:Densest subgraph
1674:
1670:
1655:of centers, the
1654:
1642:
1640:
1639:
1634:
1605:Manhattan metric
1599:of centers, the
1598:
1564:
1560:
1537:
1533:
1531:
1530:
1525:
1523:
1522:
1485:
1483:
1482:
1477:
1463:
1439:
1437:
1436:
1431:
1417:
1393:
1356:
1352:
1350:
1349:
1344:
1342:
1341:
1304:
1302:
1301:
1296:
1272:
1270:
1269:
1264:
1262:
1261:
1243:
1242:
1222:
1220:
1219:
1214:
1203:
1202:
1174:
1162:
1160:
1159:
1154:
1152:
1151:
1133:
1132:
1128:
1120:
1112:
1107:
1106:
1097:
1077:
1075:
1074:
1069:
1045:
1038:
1036:
1035:
1030:
1028:
1027:
1009:
1008:
1004:
1003:
994:
989:
988:
961:
959:
958:
953:
917:
901:
899:
898:
893:
891:
890:
872:
871:
850:
832:
830:
829:
824:
800:
792:
790:
789:
784:
782:
781:
769:
768:
755:
753:
752:
747:
729:
727:
726:
721:
676:
672:
670:
669:
664:
662:
661:
618:
616:
615:
610:
586:
584:
583:
578:
561:, which for any
553:
551:
550:
545:
533:
531:
530:
525:
513:
511:
510:
505:
484:
476:
472:
468:
466:
465:
460:
458:
457:
414:
412:
411:
406:
382:
380:
379:
374:
357:, i.e., for any
337:
333:
331:
330:
325:
323:
322:
310:
309:
292:
288:
286:
285:
280:
278:
277:
240:
224:
220:
218:
217:
212:
191:
189:
188:
183:
181:
180:
143:
136:
132:
130:
129:
124:
103:
101:
100:
95:
93:
92:
55:
51:
47:
3937:
3936:
3932:
3931:
3930:
3928:
3927:
3926:
3902:
3901:
3900:
3899:
3866:(May 1, 2018).
3864:Shachnai, Hadas
3861:
3860:
3856:
3814:
3813:
3809:
3794:
3775:
3764:
3763:
3752:
3737:
3702:
3701:
3697:
3682:
3651:
3650:
3646:
3602:
3601:
3597:
3590:
3557:
3555:
3554:
3550:
3543:
3512:
3511:
3507:
3455:
3454:
3447:
3432:
3407:
3406:
3402:
3350:
3349:
3342:
3308:
3307:
3303:
3280:10.1145/3477541
3251:
3250:
3246:
3231:
3206:
3205:
3201:
3186:
3161:
3160:
3156:
3141:
3110:
3109:
3105:
3098:
3077:
3076:
3072:
3057:
3026:
3025:
3018:
2995:10.1145/3447584
2966:
2965:
2961:
2946:
2915:
2914:
2910:
2895:
2870:
2869:
2865:
2831:
2830:
2826:
2796:
2795:
2791:
2739:
2738:
2731:
2697:
2696:
2692:
2666:
2665:
2661:
2621:
2620:
2616:
2566:
2565:
2561:
2515:
2514:
2510:
2452:
2451:
2447:
2421:
2420:
2416:
2411:
2364:
2326:
2325:
2292:
2291:
2263:
2262:
2237:
2236:
2231:
2225:
2207:
2202:
2198:
2179:
2174:
2173:
2169:
2150:
2145:
2144:
2138:
2133:
2114:
2109:
2108:
2089:
2084:
2083:
2064:
2059:
2058:
2057:with parameter
2039:
2034:
2033:
2029:
2025:
2011:
2002:
1998:
1968:
1951:
1950:
1922:
1921:
1914:
1905:
1869:
1864:
1863:
1854:. This is also
1794:
1788:
1787:
1783:
1756:
1755:
1720:
1719:
1715:
1706:is the Densest
1704:-Clique problem
1699:variant of the
1693:
1672:
1668:
1652:
1613:
1612:
1596:
1593:-center problem
1588:For the metric
1586:
1562:
1558:
1555:Euclidean space
1535:
1505:
1488:
1487:
1442:
1441:
1396:
1395:
1391:
1374:
1354:
1324:
1307:
1306:
1275:
1274:
1244:
1234:
1229:
1228:
1188:
1177:
1176:
1172:
1169:
1134:
1098:
1085:
1080:
1079:
1048:
1047:
1043:
1010:
995:
980:
969:
964:
963:
932:
931:
915:
908:
873:
854:
835:
834:
803:
802:
798:
758:
757:
732:
731:
700:
699:
689:
674:
644:
621:
620:
589:
588:
563:
562:
536:
535:
516:
515:
514:, the value of
487:
486:
482:
474:
470:
440:
417:
416:
385:
384:
359:
358:
335:
299:
298:
290:
260:
243:
242:
238:
231:
222:
194:
193:
163:
146:
145:
141:
134:
106:
105:
75:
58:
57:
53:
49:
45:
17:
12:
11:
5:
3935:
3933:
3925:
3924:
3919:
3914:
3904:
3903:
3898:
3897:
3854:
3827:(3): 702–730.
3807:
3792:
3750:
3735:
3695:
3680:
3644:
3595:
3588:
3548:
3541:
3505:
3445:
3430:
3400:
3340:
3301:
3244:
3229:
3199:
3184:
3154:
3139:
3103:
3096:
3070:
3055:
3016:
2959:
2944:
2908:
2893:
2863:
2844:(2): 583–599.
2824:
2789:
2752:(1): 546–574.
2729:
2710:(3): 207–214.
2690:
2679:(3): 195–207.
2659:
2630:: FOCS20–205.
2614:
2559:
2508:
2445:
2413:
2412:
2410:
2407:
2406:
2405:
2400:
2395:
2390:
2385:
2380:
2375:
2370:
2363:
2360:
2340:
2306:
2276:
2273:
2270:
2250:
2247:
2244:
2235:can be set to
2185:
2182:
2168:such that any
2156:
2153:
2120:
2117:
2095:
2092:
2070:
2067:
2045:
2042:
2010:
2007:
1984:
1981:
1978:
1975:
1971:
1967:
1964:
1961:
1958:
1938:
1935:
1932:
1929:
1913:
1912:Dominating set
1910:
1891:
1888:
1885:
1882:
1879:
1876:
1872:
1856:asymptotically
1843:
1839:
1835:
1832:
1829:
1826:
1823:
1820:
1817:
1811:
1806:
1803:
1798:
1771:
1767:
1763:
1739:
1736:
1733:
1730:
1727:
1692:
1689:
1632:
1629:
1626:
1623:
1620:
1585:
1579:
1521:
1518:
1515:
1512:
1508:
1504:
1501:
1498:
1495:
1475:
1472:
1469:
1466:
1462:
1458:
1455:
1452:
1449:
1429:
1426:
1423:
1420:
1416:
1412:
1409:
1406:
1403:
1373:
1363:
1340:
1337:
1334:
1331:
1327:
1323:
1320:
1317:
1314:
1294:
1291:
1288:
1285:
1282:
1260:
1257:
1254:
1251:
1247:
1241:
1237:
1212:
1209:
1206:
1201:
1198:
1195:
1191:
1187:
1184:
1168:
1165:
1150:
1147:
1144:
1141:
1137:
1131:
1126:
1123:
1118:
1115:
1110:
1105:
1101:
1095:
1092:
1088:
1067:
1064:
1061:
1058:
1055:
1026:
1023:
1020:
1017:
1013:
1007:
1002:
998:
993:
987:
983:
979:
976:
972:
951:
948:
945:
942:
939:
907:
904:
889:
886:
883:
880:
876:
870:
867:
864:
861:
857:
853:
849:
845:
842:
822:
819:
816:
813:
810:
780:
777:
772:
767:
745:
742:
739:
719:
716:
713:
710:
707:
688:
682:
660:
657:
654:
651:
647:
643:
640:
637:
634:
631:
628:
608:
605:
602:
599:
596:
576:
573:
570:
543:
523:
503:
500:
497:
494:
456:
453:
450:
447:
443:
439:
436:
433:
430:
427:
424:
404:
401:
398:
395:
392:
372:
369:
366:
321:
318:
313:
308:
276:
273:
270:
267:
263:
259:
256:
253:
250:
230:
227:
210:
207:
204:
201:
179:
176:
173:
170:
166:
162:
159:
156:
153:
122:
119:
116:
113:
91:
88:
85:
82:
78:
74:
71:
68:
65:
15:
13:
10:
9:
6:
4:
3:
2:
3934:
3923:
3920:
3918:
3915:
3913:
3910:
3909:
3907:
3893:
3889:
3885:
3881:
3877:
3873:
3869:
3865:
3858:
3855:
3850:
3846:
3842:
3838:
3834:
3830:
3826:
3822:
3818:
3811:
3808:
3803:
3799:
3795:
3789:
3785:
3781:
3774:
3773:
3768:
3761:
3759:
3757:
3755:
3751:
3746:
3742:
3738:
3732:
3728:
3724:
3719:
3714:
3710:
3706:
3699:
3696:
3691:
3687:
3683:
3677:
3672:
3667:
3663:
3659:
3655:
3648:
3645:
3640:
3636:
3632:
3628:
3623:
3618:
3614:
3610:
3606:
3599:
3596:
3591:
3585:
3581:
3577:
3572:
3567:
3563:
3552:
3549:
3544:
3538:
3533:
3528:
3524:
3520:
3516:
3509:
3506:
3501:
3497:
3493:
3489:
3485:
3481:
3476:
3471:
3467:
3463:
3459:
3452:
3450:
3446:
3441:
3437:
3433:
3427:
3423:
3419:
3415:
3411:
3404:
3401:
3396:
3392:
3388:
3384:
3380:
3376:
3371:
3366:
3362:
3358:
3354:
3347:
3345:
3341:
3336:
3332:
3328:
3324:
3320:
3316:
3312:
3305:
3302:
3297:
3293:
3289:
3285:
3281:
3277:
3272:
3267:
3263:
3259:
3255:
3248:
3245:
3240:
3236:
3232:
3226:
3222:
3218:
3214:
3210:
3203:
3200:
3195:
3191:
3187:
3181:
3177:
3173:
3169:
3165:
3158:
3155:
3150:
3146:
3142:
3136:
3132:
3128:
3123:
3118:
3114:
3107:
3104:
3099:
3093:
3089:
3085:
3081:
3074:
3071:
3066:
3062:
3058:
3052:
3047:
3042:
3038:
3034:
3030:
3023:
3021:
3017:
3012:
3008:
3004:
3000:
2996:
2992:
2987:
2982:
2978:
2974:
2970:
2963:
2960:
2955:
2951:
2947:
2941:
2937:
2933:
2928:
2923:
2919:
2912:
2909:
2904:
2900:
2896:
2890:
2886:
2882:
2878:
2874:
2867:
2864:
2859:
2855:
2851:
2847:
2843:
2839:
2835:
2828:
2825:
2819:
2814:
2809:
2804:
2800:
2793:
2790:
2785:
2781:
2777:
2773:
2769:
2765:
2760:
2755:
2751:
2747:
2743:
2736:
2734:
2730:
2725:
2721:
2717:
2713:
2709:
2705:
2701:
2694:
2691:
2686:
2682:
2678:
2674:
2670:
2663:
2660:
2655:
2651:
2647:
2643:
2638:
2633:
2629:
2625:
2618:
2615:
2610:
2606:
2601:
2596:
2591:
2586:
2582:
2578:
2574:
2570:
2569:Prieto, Elena
2563:
2560:
2555:
2551:
2546:
2541:
2536:
2531:
2527:
2523:
2519:
2512:
2509:
2506:
2504:
2499:
2492:
2488:
2483:
2478:
2473:
2468:
2464:
2460:
2456:
2449:
2446:
2441:
2437:
2433:
2429:
2425:
2418:
2415:
2408:
2404:
2401:
2399:
2396:
2394:
2391:
2389:
2386:
2384:
2381:
2379:
2376:
2374:
2371:
2369:
2366:
2365:
2361:
2359:
2338:
2304:
2288:
2274:
2271:
2268:
2248:
2245:
2242:
2234:
2228:
2222:
2218:
2212:
2210:
2183:
2180:
2154:
2151:
2142:
2118:
2115:
2093:
2090:
2068:
2065:
2043:
2040:
2023:
2019:
2015:
2014:Kernelization
2008:
2006:
1979:
1973:
1969:
1962:
1956:
1933:
1927:
1919:
1911:
1909:
1886:
1880:
1877:
1874:
1870:
1861:
1857:
1841:
1837:
1830:
1827:
1824:
1818:
1815:
1804:
1801:
1769:
1765:
1761:
1753:
1734:
1731:
1728:
1713:
1709:
1705:
1703:
1698:
1690:
1688:
1686:
1682:
1678:
1666:
1662:
1658:
1650:
1649:planar graphs
1646:
1627:
1624:
1621:
1610:
1606:
1602:
1594:
1592:
1583:
1580:
1578:
1576:
1572:
1568:
1556:
1552:
1548:
1543:
1541:
1516:
1510:
1506:
1499:
1493:
1470:
1467:
1464:
1460:
1456:
1453:
1450:
1424:
1421:
1418:
1414:
1410:
1407:
1404:
1389:
1387:
1382:
1380:
1371:
1367:
1364:
1362:
1360:
1335:
1329:
1325:
1318:
1312:
1289:
1286:
1283:
1255:
1249:
1245:
1239:
1235:
1226:
1207:
1204:
1199:
1196:
1193:
1189:
1182:
1166:
1164:
1145:
1139:
1135:
1124:
1121:
1116:
1113:
1108:
1103:
1099:
1090:
1086:
1062:
1059:
1056:
1042:
1021:
1015:
1011:
1000:
996:
991:
985:
981:
974:
970:
946:
943:
940:
929:
925:
921:
913:
905:
903:
884:
878:
874:
865:
859:
851:
847:
843:
817:
814:
811:
796:
770:
743:
740:
737:
714:
711:
708:
697:
695:
686:
683:
681:
680:
655:
649:
645:
638:
635:
632:
626:
603:
600:
597:
574:
571:
568:
560:
557:
541:
521:
498:
492:
480:
451:
445:
441:
434:
431:
428:
422:
399:
396:
393:
370:
367:
364:
356:
352:
348:
343:
341:
311:
296:
271:
265:
261:
254:
248:
236:
228:
226:
205:
199:
174:
168:
164:
157:
151:
138:
117:
111:
86:
80:
76:
69:
63:
42:
41:
37:
33:
30:
26:
23:is a type of
22:
3875:
3871:
3857:
3824:
3821:Algorithmica
3820:
3810:
3771:
3708:
3698:
3661:
3657:
3647:
3612:
3608:
3598:
3561:
3551:
3522:
3518:
3508:
3465:
3462:Algorithmica
3461:
3413:
3403:
3360:
3357:Algorithmica
3356:
3318:
3314:
3304:
3261:
3257:
3247:
3212:
3202:
3167:
3157:
3112:
3106:
3079:
3073:
3036:
3032:
2976:
2972:
2962:
2917:
2911:
2876:
2866:
2841:
2837:
2827:
2798:
2792:
2749:
2745:
2707:
2703:
2693:
2676:
2672:
2662:
2627:
2617:
2580:
2576:
2562:
2525:
2521:
2511:
2495:
2462:
2458:
2448:
2434:(1): 60–78.
2431:
2427:
2417:
2289:
2230:
2224:
2220:
2213:
2206:
2199:αβ
2137:
2012:
1915:
1707:
1701:
1697:optimization
1694:
1590:
1587:
1581:
1544:
1538:, under Gap-
1385:
1378:
1375:
1369:
1368:-median and
1365:
1357:, under Gap-
1170:
909:
906:Steiner Tree
693:
690:
684:
558:
555:
354:
344:
232:
192:time, where
139:
104:time, where
43:
20:
18:
2600:10230/36518
2583:: 209–222.
1685:cliquewidth
756:, assuming
587:computes a
3912:Algorithms
3906:Categories
3718:1711.11029
3622:1704.08868
3615:: 90–117.
3571:2209.00675
3475:1802.08563
3370:1605.02530
3271:1812.08664
3122:1708.07381
2986:1707.06499
2808:2402.09835
2759:1710.00668
2637:2005.00134
2535:1705.03581
2522:Algorithms
2472:2006.04411
2465:(6): 146.
2459:Algorithms
2409:References
1663:, and the
1607:), or the
3892:0022-0000
3878:: 30–40.
3849:253973283
3841:1432-0541
3639:0166-218X
3492:1432-0541
3387:1432-0541
3335:0022-0000
3321:: 72–93.
3296:240476191
3288:0004-5411
3065:139103417
3011:235372580
3003:1549-6325
2927:1308.3520
2858:0895-4801
2776:0895-4801
2724:0304-3975
2654:0097-5397
2609:1571-0661
2554:1999-4893
2528:(1): 10.
2503:CC BY 4.0
2491:1999-4893
2344:coNP/poly
2339:⊆
2310:coNP/poly
2305:⊆
2269:ε
2249:ε
1878:−
1828:−
1732:−
1681:treewidth
1675:with the
1665:pathwidth
1628:ε
1625:−
1553:. In the
1547:dimension
1471:ε
1468:−
1425:ε
1422:−
1290:ε
1287:−
1205:
1200:ε
1197:−
1125:ε
1117:
1109:ε
1063:ε
1041:treewidth
997:ε
947:ε
852:ε
818:ε
771:≠
738:ε
715:ε
712:−
639:ε
604:ε
569:ε
556:efficient
542:ε
522:ε
499:ε
452:ε
435:ε
400:ε
365:ε
312:≠
25:algorithm
3802:14599219
3395:46886829
3149:30474859
2673:Networks
2505:license.
2261:for any
2184:′
2155:′
2119:′
2094:′
2069:′
2044:′
1916:For the
1754:of size
1752:matching
928:APX-hard
793:and the
353:admit a
347:APX-hard
297:, e.g.,
3745:3170316
3690:4681120
3500:3532236
3239:2677556
3194:5694112
2954:6796132
2903:8554166
2784:3581913
2022:NP-hard
1584:-center
1381:-median
29:NP-hard
3890:
3847:
3839:
3800:
3790:
3743:
3733:
3688:
3678:
3637:
3586:
3539:
3498:
3490:
3440:658151
3438:
3428:
3393:
3385:
3333:
3294:
3286:
3237:
3227:
3192:
3182:
3147:
3137:
3094:
3063:
3053:
3009:
3001:
2952:
2942:
2901:
2891:
2856:
2782:
2774:
2722:
2652:
2607:
2552:
2489:
2232:α
2226:α
2223:is an
2208:α
2170:β
2139:α
1659:, the
1551:metric
1388:-means
1372:-means
1163:time.
920:W-hard
902:time.
351:W-hard
340:W-hard
291:α
239:α
142:α
50:α
46:α
3845:S2CID
3798:S2CID
3776:(PDF)
3741:S2CID
3713:arXiv
3686:S2CID
3617:arXiv
3566:arXiv
3496:S2CID
3470:arXiv
3436:S2CID
3391:S2CID
3365:arXiv
3292:S2CID
3266:arXiv
3235:S2CID
3190:S2CID
3145:S2CID
3117:arXiv
3061:S2CID
3007:S2CID
2981:arXiv
2950:S2CID
2922:arXiv
2899:S2CID
2803:arXiv
2780:S2CID
2754:arXiv
2632:arXiv
2530:arXiv
2467:arXiv
3888:ISSN
3837:ISSN
3788:ISBN
3731:ISBN
3676:ISBN
3635:ISSN
3584:ISBN
3537:ISBN
3488:ISSN
3426:ISBN
3383:ISSN
3331:ISSN
3284:ISSN
3225:ISBN
3180:ISBN
3135:ISBN
3092:ISBN
3051:ISBN
2999:ISSN
2940:ISBN
2889:ISBN
2854:ISSN
2772:ISSN
2720:ISSN
2650:ISSN
2605:ISSN
2550:ISSN
2487:ISSN
2272:>
2107:and
2001:and
1383:and
910:The
741:>
696:-cut
691:The
687:-cut
572:>
473:and
368:>
349:and
38:and
3880:doi
3829:doi
3780:doi
3723:doi
3666:doi
3627:doi
3613:264
3576:doi
3527:doi
3523:112
3480:doi
3418:doi
3375:doi
3323:doi
3319:122
3276:doi
3217:doi
3172:doi
3127:doi
3084:doi
3041:doi
3037:132
2991:doi
2932:doi
2881:doi
2846:doi
2813:doi
2764:doi
2712:doi
2708:406
2681:doi
2642:doi
2595:hdl
2585:doi
2540:doi
2477:doi
2436:doi
1862:no
1860:ETH
1695:An
1540:ETH
1359:ETH
1190:log
1114:log
342:).
3908::
3886:.
3876:93
3874:.
3870:.
3843:.
3835:.
3825:71
3823:.
3819:.
3796:.
3786:.
3769:.
3753:^
3739:.
3729:.
3721:.
3707:.
3684:.
3674:.
3662:94
3656:.
3633:.
3625:.
3607:.
3582:.
3574:.
3535:.
3517:.
3494:.
3486:.
3478:.
3466:82
3464:.
3460:.
3448:^
3434:.
3424:.
3412:.
3389:.
3381:.
3373:.
3361:81
3359:.
3355:.
3343:^
3329:.
3317:.
3313:.
3290:.
3282:.
3274:.
3262:68
3260:.
3256:.
3233:.
3223:.
3211:.
3188:.
3178:.
3166:.
3143:.
3133:.
3125:.
3090:.
3059:.
3049:.
3031:.
3019:^
3005:.
2997:.
2989:.
2977:17
2975:.
2971:.
2948:.
2938:.
2930:.
2897:.
2887:.
2875:.
2852:.
2842:25
2840:.
2836:.
2811:.
2778:.
2770:.
2762:.
2750:35
2748:.
2744:.
2732:^
2718:.
2702:.
2675:.
2671:.
2648:.
2640:.
2626:.
2603:.
2593:.
2581:78
2575:.
2548:.
2538:.
2526:11
2524:.
2520:.
2485:.
2475:.
2463:13
2461:.
2457:.
2432:51
2430:.
2426:.
2334:NP
2300:NP
2287:.
2005:.
1908:.
1687:.
1575:XP
1361:.
383:a
137:.
19:A
3894:.
3882::
3851:.
3831::
3804:.
3782::
3747:.
3725::
3715::
3692:.
3668::
3641:.
3629::
3619::
3592:.
3578::
3568::
3558:k
3545:.
3529::
3502:.
3482::
3472::
3442:.
3420::
3397:.
3377::
3367::
3337:.
3325::
3298:.
3278::
3268::
3241:.
3219::
3196:.
3174::
3151:.
3129::
3119::
3100:.
3086::
3067:.
3043::
3013:.
2993::
2983::
2956:.
2934::
2924::
2905:.
2883::
2860:.
2848::
2821:.
2815::
2805::
2786:.
2766::
2756::
2726:.
2714::
2687:.
2683::
2677:1
2656:.
2644::
2634::
2611:.
2597::
2587::
2556:.
2542::
2532::
2493:.
2479::
2469::
2442:.
2438::
2275:0
2246:+
2243:1
2203:I
2181:I
2152:I
2134:k
2116:k
2091:I
2066:k
2041:I
2030:k
2026:I
2003:f
1999:g
1983:)
1980:1
1977:(
1974:O
1970:n
1966:)
1963:k
1960:(
1957:f
1937:)
1934:k
1931:(
1928:g
1906:k
1890:)
1887:1
1884:(
1881:o
1875:1
1871:k
1842:2
1838:/
1834:)
1831:1
1825:k
1822:(
1819:k
1816:=
1810:)
1805:2
1802:k
1797:(
1784:k
1770:2
1766:/
1762:k
1738:)
1735:1
1729:k
1726:(
1716:k
1708:k
1702:k
1673:k
1669:k
1653:k
1631:)
1622:2
1619:(
1597:k
1591:k
1582:k
1563:k
1559:d
1536:f
1520:)
1517:1
1514:(
1511:O
1507:n
1503:)
1500:k
1497:(
1494:f
1474:)
1465:e
1461:/
1457:8
1454:+
1451:1
1448:(
1428:)
1419:e
1415:/
1411:2
1408:+
1405:1
1402:(
1392:k
1386:k
1379:k
1370:k
1366:k
1355:f
1339:)
1336:1
1333:(
1330:O
1326:n
1322:)
1319:k
1316:(
1313:f
1293:)
1284:2
1281:(
1259:)
1256:1
1253:(
1250:O
1246:n
1240:k
1236:3
1211:)
1208:n
1194:2
1186:(
1183:O
1173:k
1149:)
1146:1
1143:(
1140:O
1136:n
1130:)
1122:t
1104:2
1100:t
1094:(
1091:O
1087:2
1066:)
1060:+
1057:1
1054:(
1044:t
1025:)
1022:1
1019:(
1016:O
1012:n
1006:)
1001:4
992:/
986:2
982:k
978:(
975:O
971:2
950:)
944:+
941:1
938:(
916:k
888:)
885:1
882:(
879:O
875:n
869:)
866:k
863:(
860:O
856:)
848:/
844:k
841:(
821:)
815:+
812:1
809:(
799:k
779:P
776:N
766:P
744:0
718:)
709:2
706:(
694:k
685:k
675:f
659:)
656:1
653:(
650:O
646:n
642:)
636:,
633:k
630:(
627:f
607:)
601:+
598:1
595:(
575:0
502:)
496:(
493:g
483:k
475:g
471:f
455:)
449:(
446:g
442:n
438:)
432:,
429:k
426:(
423:f
403:)
397:+
394:1
391:(
371:0
336:k
320:P
317:N
307:P
275:)
272:1
269:(
266:O
262:n
258:)
255:k
252:(
249:f
223:n
209:)
206:k
203:(
200:f
178:)
175:1
172:(
169:O
165:n
161:)
158:k
155:(
152:f
135:n
121:)
118:k
115:(
112:f
90:)
87:1
84:(
81:O
77:n
73:)
70:k
67:(
64:f
54:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.