96:
from a problem A to a problem B, then any polynomial-time solution for B can be composed with that reduction to obtain a polynomial-time solution for the problem A. Similarly, our goal in defining PTAS reductions is so that given a PTAS reduction from an optimization problem A to a problem B, a PTAS
496:
410:
448:
362:
83:
242:
283:
313:
207:
161:
453:
367:
416:
330:
51:
37:
520:
89:
25:
625:
601:
574:
620:
17:
504:
imply PTAS reductions. As a result, one may show the existence of a PTAS reduction via a L-reduction instead.
173:
maps error parameters for solutions to instances of problem A to error parameters for solutions to problem B.
212:
247:
105:
Formally, we define a PTAS reduction from A to B using three polynomial-time computable functions,
292:
93:
29:
554:
41:
33:
183:
137:
8:
491:{\displaystyle {\text{A}}\not \in {\text{PTAS}}\implies {\text{B}}\not \in {\text{PTAS}}}
580:
48:. Notationally, if there is a PTAS reduction from a problem A to a problem B, we write
597:
570:
605:
584:
511:, the class of optimization problems with constant-factor approximation algorithms.
562:
596:
Ingo
Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms.
405:{\displaystyle {\text{B}}\in {\text{PTAS}}\implies {\text{A}}\in {\text{PTAS}}}
614:
97:
for B can be composed with the reduction to obtain a PTAS for the problem A.
566:
163:
in B, and an error parameter ε and produces an approximate solution to
525:
501:
559:
Proceedings of
Computational Complexity. Twelfth Annual IEEE Conference
244:
times worse than the optimal solution, then the corresponding solution
134:
of problem A, an approximate solution to the corresponding problem
561:. Washington, D.C.: IEEE Computer Society. pp. 262–273.
530:
508:
45:
324:
From the definition it is straightforward to show that:
443:{\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}
357:{\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}
78:{\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}
555:"A short guide to approximation preserving reductions"
124:
maps instances of problem A to instances of problem B.
456:
419:
370:
333:
295:
250:
215:
186:
140:
54:
44:
for certain classes of optimization problems such as
507:PTAS reductions are used to define completeness in
490:
442:
404:
356:
307:
277:
236:
201:
155:
77:
36:. It preserves the property that a problem has a
612:
548:
546:
474:
470:
388:
384:
552:
543:
613:
315:times worse than the optimal solution.
289:(an instance of problem A) is at most
209:(an instance of problem B) is at most
604:. Chapter 8, pp. 110–111.
237:{\displaystyle 1+\alpha (\epsilon )}
38:polynomial time approximation scheme
90:polynomial-time many-one reductions
13:
521:Approximation-preserving reduction
26:approximation-preserving reduction
14:
637:
117:, with the following properties:
278:{\displaystyle g(x,y,\epsilon )}
18:computational complexity theory
471:
385:
272:
254:
231:
225:
196:
190:
150:
144:
28:that is often used to perform
1:
553:Crescenzi, Pierluigi (1997).
536:
319:
100:
40:(PTAS) and is used to define
7:
514:
308:{\displaystyle 1+\epsilon }
10:
642:
626:Approximation algorithms
567:10.1109/CCC.1997.612321
92:, if we can describe a
621:Reduction (complexity)
492:
444:
406:
358:
309:
279:
238:
203:
157:
79:
493:
445:
407:
359:
310:
280:
239:
204:
158:
80:
34:optimization problems
32:between solutions to
606:Google Books preview
454:
417:
368:
331:
293:
248:
213:
202:{\displaystyle f(x)}
184:
156:{\displaystyle f(x)}
138:
52:
488:
440:
402:
354:
305:
275:
234:
199:
153:
130:takes an instance
75:
486:
478:
468:
460:
438:
432:
423:
400:
392:
382:
374:
352:
346:
337:
73:
67:
58:
633:
589:
588:
550:
497:
495:
494:
489:
487:
484:
479:
476:
469:
466:
461:
458:
449:
447:
446:
441:
439:
436:
434:
433:
430:
424:
421:
411:
409:
408:
403:
401:
398:
393:
390:
383:
380:
375:
372:
363:
361:
360:
355:
353:
350:
348:
347:
344:
338:
335:
314:
312:
311:
306:
284:
282:
281:
276:
243:
241:
240:
235:
208:
206:
205:
200:
176:If the solution
162:
160:
159:
154:
84:
82:
81:
76:
74:
71:
69:
68:
65:
59:
56:
641:
640:
636:
635:
634:
632:
631:
630:
611:
610:
593:
592:
577:
551:
544:
539:
517:
483:
475:
465:
457:
455:
452:
451:
435:
429:
425:
420:
418:
415:
414:
397:
389:
379:
371:
369:
366:
365:
349:
343:
339:
334:
332:
329:
328:
322:
294:
291:
290:
249:
246:
245:
214:
211:
210:
185:
182:
181:
139:
136:
135:
103:
70:
64:
60:
55:
53:
50:
49:
12:
11:
5:
639:
629:
628:
623:
609:
608:
591:
590:
575:
541:
540:
538:
535:
534:
533:
528:
523:
516:
513:
499:
498:
482:
473:
464:
428:
412:
396:
387:
378:
342:
321:
318:
317:
316:
304:
301:
298:
274:
271:
268:
265:
262:
259:
256:
253:
233:
230:
227:
224:
221:
218:
198:
195:
192:
189:
174:
168:
152:
149:
146:
143:
125:
102:
99:
88:With ordinary
63:
22:PTAS reduction
9:
6:
4:
3:
2:
638:
627:
624:
622:
619:
618:
616:
607:
603:
602:3-540-21045-8
599:
595:
594:
586:
582:
578:
576:0-8186-7907-7
572:
568:
564:
560:
556:
549:
547:
542:
532:
529:
527:
524:
522:
519:
518:
512:
510:
505:
503:
480:
462:
426:
413:
394:
376:
340:
327:
326:
325:
302:
299:
296:
288:
269:
266:
263:
260:
257:
251:
228:
222:
219:
216:
193:
187:
179:
175:
172:
169:
166:
147:
141:
133:
129:
126:
123:
120:
119:
118:
116:
112:
108:
98:
95:
91:
86:
61:
47:
43:
39:
35:
31:
27:
23:
19:
558:
506:
502:L-reductions
500:
323:
286:
177:
170:
164:
131:
127:
121:
114:
110:
106:
104:
87:
42:completeness
21:
15:
526:L-reduction
615:Categories
537:References
320:Properties
101:Definition
30:reductions
472:⟹
427:≤
395:∈
386:⟹
377:∈
341:≤
303:ϵ
270:ϵ
229:ϵ
223:α
94:reduction
62:≤
585:18911241
515:See also
481:∉
463:∉
600:
583:
573:
171:α
115:α
113:, and
24:is an
581:S2CID
598:ISBN
571:ISBN
485:PTAS
467:PTAS
450:and
431:PTAS
399:PTAS
381:PTAS
364:and
345:PTAS
66:PTAS
20:, a
563:doi
531:APX
509:APX
285:to
180:to
46:APX
16:In
617::
579:.
569:.
557:.
545:^
109:,
85:.
587:.
565::
477:B
459:A
437:B
422:A
391:A
373:B
351:B
336:A
300:+
297:1
287:x
273:)
267:,
264:y
261:,
258:x
255:(
252:g
232:)
226:(
220:+
217:1
197:)
194:x
191:(
188:f
178:y
167:.
165:x
151:)
148:x
145:(
142:f
132:x
128:g
122:f
111:g
107:f
72:B
57:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.