(Basic Feasibility & Iterated Rounding) Suppose you are given a matrix A = {0, 1}*** such...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(Basic Feasibility & Iterated Rounding) Suppose you are given a matrix A = {0, 1}*** such that each column of A has at most s ones, i.e., column sparsity is s. We want to find a coloring {-1, +1}" such that ||A|||||| is as small as possible. (a) Suppose we choose & uniformly at random, i.e., & is -1 or +1 with independently with equal probability. Show that in expectation ||Ae is O(n logn). Next, we will analyze the following polynomial time algorithm to find a coloring (-1, +1]" such that AlO(s), which is much better than O(n logn) when s is small. The algorithm will iteratively color more and more columns of A. Initially, all columns are "uncolored" and a column de gets "colored" when &t is defined. In any iteration, if the number of remaining uncolored columns is at most 2s, color them arbitrarily and halt. . Otherwise, we solve an LP with fractional variables denoting the fractional col- ors of the uncolored columns. For every row i that contains more than 28 un- colored ones, put an LP constraint that its fractional discrepancy is zero, i.e., a(i)Y = 0 where Y, denotes LP variable , -1,1] for uncolored columns t, and Y, denotes constant &, for colored columns t. Find a basic solution of the above LP, and for any uncolored column t that gets z {-1, +1} in this basic solution, we permanently set its e to that color. Repeat. (b) Show that in any iteration, the number of row constraints that we put is at most half the number of currently uncolored columns. Deduce that a basic solution will integrally color at least half the columns in each iteration. (c) Show that this algorithm obtains a solution with discrepancy O(s). This means, e.g., that if each column has O(1) non-zero entries then the discrepancy is O(1). Remark: There is nothing special about A = {0, 1] xn vs. A = [0, 1]x, i.e., having T n columns and real entries. We can easily extend the above result using the idea. of finding a basic solution in the beginning with at most n uncolored columns. (Basic Feasibility & Iterated Rounding) Suppose you are given a matrix A = {0, 1}*** such that each column of A has at most s ones, i.e., column sparsity is s. We want to find a coloring {-1, +1}" such that ||A|||||| is as small as possible. (a) Suppose we choose & uniformly at random, i.e., & is -1 or +1 with independently with equal probability. Show that in expectation ||Ae is O(n logn). Next, we will analyze the following polynomial time algorithm to find a coloring (-1, +1]" such that AlO(s), which is much better than O(n logn) when s is small. The algorithm will iteratively color more and more columns of A. Initially, all columns are "uncolored" and a column de gets "colored" when &t is defined. In any iteration, if the number of remaining uncolored columns is at most 2s, color them arbitrarily and halt. . Otherwise, we solve an LP with fractional variables denoting the fractional col- ors of the uncolored columns. For every row i that contains more than 28 un- colored ones, put an LP constraint that its fractional discrepancy is zero, i.e., a(i)Y = 0 where Y, denotes LP variable , -1,1] for uncolored columns t, and Y, denotes constant &, for colored columns t. Find a basic solution of the above LP, and for any uncolored column t that gets z {-1, +1} in this basic solution, we permanently set its e to that color. Repeat. (b) Show that in any iteration, the number of row constraints that we put is at most half the number of currently uncolored columns. Deduce that a basic solution will integrally color at least half the columns in each iteration. (c) Show that this algorithm obtains a solution with discrepancy O(s). This means, e.g., that if each column has O(1) non-zero entries then the discrepancy is O(1). Remark: There is nothing special about A = {0, 1] xn vs. A = [0, 1]x, i.e., having T n columns and real entries. We can easily extend the above result using the idea. of finding a basic solution in the beginning with at most n uncolored columns.
Expert Answer:
Related Book For
Introduction to Data Mining
ISBN: 978-0321321367
1st edition
Authors: Pang Ning Tan, Michael Steinbach, Vipin Kumar
Posted Date:
Students also viewed these algorithms questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...
-
CASE STUDY. Case Study Chapters 1 and 2. Please post both case studies in Assignment Drop Box as one MS Word apa formate document. Note: See template provided for case study papers. Chapter 1 - Listo...
-
What does the future look like for Health Care Information Technology in terms of software development, education, research, and practices? What challenges could arise?
-
Forrest runs Y Not Flowers, Inc. (YNF), a wholesale flower distributor with stores in several major metropolitan areas of the U.S. He is considering expanding his business, but he thinks his current...
-
A system comprising of single phase is known as: (a) Open system (b) Closed system (c) Homogeneous system (d) Heterogeneous system
-
Quality Center began operations on July 1. It uses a perpetual inventory system. During July the company had the following purchases and sales. Instructions (a) Determine the ending inventory under a...
-
The XYZ Company issued discount debt bonds with the nominal value of $100,000.The bonds have a maturity period of 5 year and a coupon rate of 6% annually.Calculate the issue price of the bonds taking...
-
What do you think of the incident and the way the club handled it? Do you think the club should have conducted a needs analysis before deciding on what they will do? What information would they have...
-
Development economics studies the transformation of emerging nations into more prosperous one and it seeks to understand and shape the country's macro and microeconomics policies in order to lift...
-
In December of 2017, the US Government signed the Tax Cuts and Jobs Act (TCJA) into law. The TCJA had four goals; tax relief for middle-income families, simplification for individuals, economic...
-
Amazon, Inc. Presentation Your chief executive officer (CEO) has asked you to present the company's (Amazon, Inc.) process on making decisions under risks and uncertainty at the annual shareholders'...
-
Consider the Bertrand duopoly discussed in class. Assume each firm has constant marginal cost c = 10 and zero fixed cost. Each firm chooses a price Pi 0. The market demand is given by Q = 130 P,...
-
Amy Austin is considering going back to school at nights. She will either get a masters degree in Accounting (her first degree is in Accounting) or an MBA She has calculated the net present value...
-
Write a reflective essay to critically evaluate the usefulness of change management models and recommend one specific model to strategic option identified in Task 2.. Task2: You should also explain...
-
The trade-off theory relies on the threat of financial distress. But why should a public corporation ever have to land in financial distress? According to the theory, the firm should operate at the...
-
For the data set with the attributes given below, describe how you would convert it into a binary transaction data set appropriate for association analysis. Specifically, indicate for each attribute...
-
Identify at least two advantages and two disadvantages of using color to visually represent information.
-
Describe how you would create visualizations to display information that describes the following types of systems. Be sure to address the following issues: Representation. How will you map objects,...
-
Apple stock is selling for \($120\) per share. Call options with a \($117\) exercise price are priced at \($12.\) What is the intrinsic value of the option, and what is the time value?
-
Ibrahim bought 200 shares of a stock trading in the Abu Dhabi Securities Exchange at AED 12 (United Arab Emirates dirham) per share. Over time, the price of the stock increased to AED 18 per share....
-
Refer to Problem 14.9. What would the loss of the seller of the put option be if, at expiration, XLB is trading at \($20?\) What would the profit of the seller be if, at expiration, XLB is trading at...
Study smarter with the SolutionInn App