We consider the problem of finding inscribed boxes and axis-aligned inscribed boxes of maximum volume, inside a compact and solid convex set. Our algorithms are capable of solving these two problems in any such set that can be represented with finite number of convex inequalities. For the axis-aligned case, we formulate the problem for higher dimensions and present an exact optimization algorithm which solves the problem in @math time, where @math is the dimension and @math is the number of inequalities defining the convex set. For the general case, after formulating the problem for higher dimensions we investigate the traditional 2-dimensional problem, which is in the literature merely considered for convex polygons, for a broad range of convex sets. We first present a new exact algorithm that finds the largest inscribed axis-aligned rectangle in such convex sets for any given direction of axes in @math time. Using this exact algorithm as a subroutine, we present an @math -approximation algorithm that computes @math -approximation to the largest inscribed rectangle with computational complexity of @math . Finally, we show that how this running time can be improved to @math with a @math pre-processing time when the convex set is a polygon.
To our knowledge, except Amenta's model @cite_28 for LIAR and the model of @cite_22 for LIR, no other optimization based algorithm published so far for these two problems. Again, except Amenta's model for LIAR @cite_28 , we are not aware of any model or algorithm for the higher dimension problem. Our optimization model for LIAR is much more efficient than Amenta's model. Also none of the algorithms in the literature are able to solve both problems, while our parametric approach is able to do so in 2-dimensional case. Moreover, except 's algorithm @cite_22 , no algorithm is published so far for either of these problems that is capable of dealing with other geometric convex sets such as ellipses and not just polygons. In 's algorithm @cite_22 it is not clear whether those two queries are doable for any convex set and if yes what would @math be in their algorithm's running time. Our algorithm is unique in the sense that its performance depends to the number of inequalities defining a convex set, e.g. while for a polygon this is @math for an ellipse this is one.
@cite_28 @cite_22
2473549844 2068852191 2170546552 2001663593
We consider the adversarial convex bandit problem and we build the first @math -time algorithm with @math -regret for this problem. To do so we introduce three new ideas in the derivative-free optimization literature: (i) kernel methods, (ii) a generalization of Bernoulli convolutions, and (iii) a new annealing schedule for exponential weights (with increasing learning rate). The basic version of our algorithm achieves @math -regret, and we show that a simple variant of this algorithm can be run in @math -time per step at the cost of an additional @math factor in the regret. These results improve upon the @math -regret and @math -time result of the first two authors, and the @math -regret and @math -time result of Hazan and Li. Furthermore we conjecture that another variant of the algorithm could achieve @math -regret, and moreover that this regret is unimprovable (the current best lower bound being @math and it is achieved with linear functions). For the simpler situation of zeroth order stochastic convex optimization this corresponds to the conjecture that the optimal query complexity is of order @math . We consider the makespan-minimization problem on unrelated machines in the context of algorithmic mechanism design. No truthful mechanisms with non-trivial approximation guarantees are known for this multidimensional domain. We study a well-motivated special case (also a multidimensional domain), where the processing time of a job on each machine is either "low" or "high." We give a general technique to convert any c-approximation algorithm (in a black-box fashion) to a 3c-approximation truthful-in-expectation mechanism. Our construction uses fractional truthful mechanisms as a building block, and builds upon a technique of Lavi and Swamy [Lavi, R., Swamy, C., 2005. Truthful and near-optimal mechanism design via linear programming. In: Proc. 46th FOCS, pp. 595-604]. When all jobs have identical low and high values, we devise a deterministic 2-approximation truthful mechanism. The chief novelty of our results is that we do not utilize explicit price definitions to prove truthfulness. Instead we design algorithms that satisfy cycle monotonicity [Rochet, J., 1987. A necessary and sufficient condition for rationalizability in a quasilinear context. J. Math. Econ. 16, 191-200], a necessary and sufficient condition for truthfulness in multidimensional settings; this is the first work that leverages this characterization. Mulmuley [Mul12a] recently gave an explicit version of Noether’s Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In this work, we show this is not the case. That is, we improve Mulmuley’s reduction and correspondingly weaken the conjecture regarding PIT needed to give explicit Noether Normalization. We then observe that the weaker conjecture has recently been nearly settled by the authors ([FS12]), who gave quasipolynomial size hitting sets for the class of read-once oblivious algebraic branching programs (ROABPs). This gives the desired explicit Noether Normalization unconditionally, up to quasipolynomial factors. As a consequence of our proof we give a deterministic parallel polynomial-time algorithm for deciding if two matrix tuples have intersecting orbit closures, under simultaneous conjugation. We also study the strength of conjectures that Mulmuley requires to obtain similar results as ours. We prove that his conjectures are stronger, in the sense that the computational model he needs PIT algorithms for is equivalent to the well-known algebraic branching program (ABP) model, which is provably stronger than the ROABP model. Finally, we consider the depth-3 diagonal circuit model as defined by Saxena [Sax08], as PIT algorithms for this model also have implications in Mulmuley’s work. Previous work (such as [ASS12] and [FS12]) have given quasipolynomial size hitting sets for this model. In this work, we give a much simpler construction of such hitting sets, using techniques of Shpilka and Volkovich [SV09]. par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degreeror bounded “width.” Specifically: We prove that the Max 3SAT problem on instances where each variable occurs in at most B clauses, is hard to approximate to within a factor @math , unless @math . H stad [18] proved that the problem is approximable to within a factor @math in polynomial time, and that is hard to approximate to within a factor @math . Our result uses a new randomized reduction from general instances of Max 3SAT to bounded-occurrences instances. The randomized reduction applies to other Max SNP problems as well. We observe that the Set Cover problem on instances where each set has size at most B is hard to approximate to within a factor @math unless @math . The result follows from an appropriate setting of parameters in Feige's reduction [11]. This is essentially tight in light of the existence of @math -approximate algorithms [20, 23, 9] We present a new PCP construction, based on applying parallel repetition to the inner verifier,'' and we provide a tight analysis for it. Using the new construction, and some modifications to known reductions from PCP to Hitting Set, we prove that Hitting Set with sets of size B is hard to approximate to within a factor @math . The problem can be approximated to within a factor B [19], and it is the Vertex Cover problem for B =2. The relationship between hardness of approximation and set size seems to have not been explored before. We observe that the Independent Set problem on graphs having degree at most B is hard to approximate to within a factor @math , unless P = NP . This follows from a comination of results by Clementi and Trevisan [28] and Reingold, Vadhan and Wigderson [27]. It had been observed that the problem is hard to approximate to within a factor @math unless P = NP [1]. An algorithm achieving factor @math is also known [21, 2, 30, 16 .