DOC PREVIEW
TAMU CSCE 689 - w2

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IntroductionIntegers and Their SumsGraphs and Their Cliques and CutsSets and Their SubsetsSpace and Time Complexity of ExactAlgorithms:Some Open ProblemsGerhard J. WoegingerTU Eindhoven, The [email protected]. We discuss open questions around worst case time and spacebounds for NP-hard problems. We are interested in exponential timesolutions for these problems with a relatively good worst case behavior.1 IntroductionEvery problem in NP can be solved in exponential time by exhaustive search:Recall that a decision problem is in NP, if and only if there exists a polynomialtime decidable relation R(x, y) and a polynomial m(|x|) such that for every YES-instance x, there exists a YES-certificate y with |y|≤m(x)andR(x, y). A trivialexact algorithm for solving instance x enumerates all possible strings y withlengths up to m(|x|), and checks whether any of them yields a YES-certificate.Up to polynomial factors that depend on the evaluation time of R(x, y), thisyields an exponential running time of 2m(x).A natural question is: Can we do better than this trivial enumerative al-gorithm? Interestingly, for many combinatorial optimization problems the an-swer is YES. Early examples include an O∗(1.4422n) algorithm for deciding3-colorability of an n-vertex graph by Lawler [21]; an O∗(1.2599n) algorithmfor finding a maximum independent set in an n-vertex graph by Tarjan & Tro-janowski [24]; an O∗(1.4142n) algorithm for the SUBSET-SUM problems withn integers by Horowitz & Sahni [18]. (The notation O∗(f(n)) is explained at theend of this section.) Woeginger [26] surveys many results in this area.For some optimization problems, we can reach an improved time complexity,but it seems that we have to pay for this with an exponential space complexity.Note that algorithms with exponential space complexities are absolutely uselessfor real life applications. In this paper, we discuss a number of results around fastexponential time algorithms that come with exponential space complexities. Wepresent approaches, tricks, related polynomially solvable problems, and relatedopen questions.Notation. Throughout this paper, we will use a modified big-Oh notation thatsuppresses polynomially bounded terms. For a positive real constant c,wewriteO∗(cn) for a time complexity of the form O(cn· poly(n)). The notations Ω∗(cn)and Θ∗(cn) are defined analogously.R. Downey, M. Fellows, and F. Dehne (Eds.): IWPEC 2004, LNCS 3162, pp. 281–290, 2004.c Springer-Verlag Berlin Heidelberg 2004282 Gerhard J. Woeginger2 Integers and Their SumsWe start this section with a couple of polynomially solvable problems: An inputto the first problem “k-SUM” consists of m integers a1,...,amand a goal sum S.The problem is to decide whether there are k of these integers that add up to S.An input to the second problem “Table-k-SUM” consists of a k × m table and agoal sum S;theentriesinrowi of the table are denoted by Ri(1),...,Ri(m). Theproblem is to decide whether one can choose k integers from this table, exactlyone from each row, that add up to S.Inbothproblems,thenumberk is a fixedinteger that is not part of the input. Both problems are closely related, and theycan be reduced to each other in linear time (Erickson [12]). Both problems aretrivially solvable in polynomial time O(mk).Here is how to get a better time complexity for Table-2-SUM: Sort the entriesin the first row. Then for j =1,...,m perform a binary search for the valueS − R2(j) in this sorted first row. If the search succeeds at R1(i), then R1(i)=S − R2(j) and the answer is YES. If all searches fail, then the answer is NO.Fact. Table-2-SUM can be solved in O(m log m) time and O(m) space.The same approach also yields fast algorithms for Table-k-SUM for all k ≥ 3:Compute the sum of every k/2-tuple of integers that has one entry in each ofthe first k/2 rows; these sums form the first row in a new table. Computethe sum of every k/2-tuple of integers that has one entry in each of the lastk/2 rows; these sums form the second row in the new table. Apply the abovealgorithm to this new instance of Table-2-SUM.Fact. Table-k-SUM can be solved in O(m k/2log m) time and O(m k/2) space.For o dd k, the time complexity can be slightly improved to O(m k/2); seefor instance Erickson [11]. In particular, the 3-SUM problem can be solved inO(m2) time. We will not go into details, since in this paper we really do not careabout logarithmic factors. The main drawback of all these algorithms is theirhorrible space complexity.Schroeppel & Shamir [23] improve the space complexity for Table-4-SUMby using a data structure that enumerates the m2sums R1(i)+R2(j)with1 ≤ i, j ≤ m in non-decreasing order. This data structure uses only O(m) space.Every time we kick it, it starts working for O(log m) time steps, and then spitsout the next larger sum R1(i)+R2(j). The data structure is based on a balancedsearch tree that supports deletions, insertions, and extracting the minimum withlogarithmic work per operation. It is built as follows: In a preprocessing step, webring the entries in the second row into non-decreasing order. As a consequence,we have for every fixed index i thatR1(i)+R2(1) ≤ R1(i)+R2(2) ≤ ··· ≤ R1(i)+R2(m).For every index i (1 ≤ i ≤ m), the data structure stores the pair (i, j)thatcorresponds to the first unvisited sum R1(i)+R2(j) in this ordering. Wheneverthe data structure is kicked, it extracts and deletes the pair (i, j) with minimumSpace and Time Complexity of Exact Algorithms: Some Open Problems 283sum, and inserts the pair (i, j + 1) instead. All in all, the enumeration of the m2sums costs O(m2log m)time.Schroeppel & Shamir [23] use two such data structures; the first one generatesthe sums x = R1(i)+R2(j) in non-decreasing order, whereas the second onegenerates the sums y = R3(s)+R4(t) in non-increasing order. Whenever x+y<S holds, the current value of x is too small for reaching the goal sum S;wereplace it by the next larger sum R1(i)+R2(j) from the first data structure.Whenever x+y>Sholds, the current value of y is too large for reaching the goalsum S; we replace it by the next smaller sum R3(s)+R4(t) from the second datastructure. These steps are repeated over and over again, until one data structurebecomes empty (answer NO) or until we reach x + y = S (answer YES).Fact. Table-4-SUM can be solved in O(m2log m) time and O(m) space.Open problem 1(a) Is there an O(m3log m) time


View Full Document

TAMU CSCE 689 - w2

Documents in this Course
slides

slides

10 pages

riccardo2

riccardo2

33 pages

ffd

ffd

33 pages

intro

intro

23 pages

slides

slides

19 pages

p888-ju

p888-ju

8 pages

w1

w1

23 pages

vfsd

vfsd

8 pages

subspace

subspace

48 pages

chapter2

chapter2

20 pages

MC

MC

41 pages

w3

w3

8 pages

Tandem

Tandem

11 pages

meanvalue

meanvalue

46 pages

CS689-MD

CS689-MD

17 pages

VGL

VGL

8 pages

ssq

ssq

10 pages

Load more
Download w2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view w2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view w2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?