{"data":{"id":"10.48550/arxiv.1412.3507","type":"dois","attributes":{"doi":"10.48550/arxiv.1412.3507","prefix":"10.48550","suffix":"arxiv.1412.3507","identifiers":[{"identifier":"1412.3507","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1412.3507"}],"creators":[{"name":"Azar, Yossi","nameType":"Personal","givenName":"Yossi","familyName":"Azar","affiliation":[],"nameIdentifiers":[]},{"name":"Cohen, Ilan Reuven","nameType":"Personal","givenName":"Ilan Reuven","familyName":"Cohen","affiliation":[],"nameIdentifiers":[]},{"name":"Panigrahi, Debmalya","nameType":"Personal","givenName":"Debmalya","familyName":"Panigrahi","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Online Covering with Convex Objectives and Applications"}],"publisher":"arXiv","container":{},"publicationYear":2014,"subjects":[{"lang":"en","subject":"Data Structures and Algorithms (cs.DS)","subjectScheme":"arXiv"},{"lang":"en","subject":"Distributed, Parallel, and Cluster Computing (cs.DC)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2014-12-11T00:35:03Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2014-12-12T01:04:11Z","dateType":"Updated","dateInformation":"v1"},{"date":"2014-12","dateType":"Available","dateInformation":"v1"},{"date":"2014","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"We give an algorithmic framework for minimizing general convex objectives (that are differentiable and monotone non-decreasing) over a set of covering constraints that arrive online. This substantially extends previous work on online covering for linear objectives (Alon {\\em et al.}, STOC 2003) and online covering with offline packing constraints (Azar {\\em et al.}, SODA 2013). To the best of our knowledge, this is the first result in online optimization for generic non-linear objectives; special cases of such objectives have previously been considered, particularly for energy minimization. As a specific problem in this genre, we consider the unrelated machine scheduling problem with startup costs and arbitrary $\\ell_p$ norms on machine loads (including the surprisingly non-trivial $\\ell_1$ norm representing total machine load). This problem was studied earlier for the makespan norm in both the offline (Khuller~{\\em et al.}, SODA 2010; Li and Khuller, SODA 2011) and online settings (Azar {\\em et al.}, SODA 2013). We adapt the two-phase approach of obtaining a fractional solution and then rounding it online (used successfully to many linear objectives) to the non-linear objective. The fractional algorithm uses ideas from our general framework that we described above (but does not fit the framework exactly because of non-positive entries in the constraint matrix). The rounding algorithm uses ideas from offline rounding of LPs with non-linear objectives (Azar and Epstein, STOC 2005; Kumar {\\em et al.}, FOCS 2005). Our competitive ratio is tight up to a logarithmic factor. Finally, for the important special case of total load ($\\ell_1$ norm), we give a different rounding algorithm that obtains a better competitive ratio than the generic rounding algorithm for $\\ell_p$ norms. We show that this competitive ratio is asymptotically tight.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xNDEyLjM1MDc8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xNDEyLjM1MDc8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+QXphciwgWW9zc2k8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPllvc3NpPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkF6YXI8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+Q29oZW4sIElsYW4gUmV1dmVuPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5JbGFuIFJldXZlbjwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5Db2hlbjwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5QYW5pZ3JhaGksIERlYm1hbHlhPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5EZWJtYWx5YTwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5QYW5pZ3JhaGk8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPk9ubGluZSBDb3ZlcmluZyB3aXRoIENvbnZleCBPYmplY3RpdmVzIGFuZCBBcHBsaWNhdGlvbnM8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMTQ8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5EYXRhIFN0cnVjdHVyZXMgYW5kIEFsZ29yaXRobXMgKGNzLkRTKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPkRpc3RyaWJ1dGVkLCBQYXJhbGxlbCwgYW5kIENsdXN0ZXIgQ29tcHV0aW5nIChjcy5EQyk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCBzdWJqZWN0U2NoZW1lPSJGaWVsZHMgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neSAoRk9TKSI+Rk9TOiBDb21wdXRlciBhbmQgaW5mb3JtYXRpb24gc2NpZW5jZXM8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE0LTEyLTExVDAwOjM1OjAzWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE0LTEyLTEyVDAxOjA0OjExWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTQtMTI8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlByZXByaW50Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MTwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL25vbmV4Y2x1c2l2ZS1kaXN0cmliLzEuMC8iPmFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZTwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPldlIGdpdmUgYW4gYWxnb3JpdGhtaWMgZnJhbWV3b3JrIGZvciBtaW5pbWl6aW5nIGdlbmVyYWwgY29udmV4IG9iamVjdGl2ZXMgKHRoYXQgYXJlIGRpZmZlcmVudGlhYmxlIGFuZCBtb25vdG9uZSBub24tZGVjcmVhc2luZykgb3ZlciBhIHNldCBvZiBjb3ZlcmluZyBjb25zdHJhaW50cyB0aGF0IGFycml2ZSBvbmxpbmUuIFRoaXMgc3Vic3RhbnRpYWxseSBleHRlbmRzIHByZXZpb3VzIHdvcmsgb24gb25saW5lIGNvdmVyaW5nIGZvciBsaW5lYXIgb2JqZWN0aXZlcyAoQWxvbiB7XGVtIGV0IGFsLn0sIFNUT0MgMjAwMykgYW5kIG9ubGluZSBjb3ZlcmluZyB3aXRoIG9mZmxpbmUgcGFja2luZyBjb25zdHJhaW50cyAoQXphciB7XGVtIGV0IGFsLn0sIFNPREEgMjAxMykuIFRvIHRoZSBiZXN0IG9mIG91ciBrbm93bGVkZ2UsIHRoaXMgaXMgdGhlIGZpcnN0IHJlc3VsdCBpbiBvbmxpbmUgb3B0aW1pemF0aW9uIGZvciBnZW5lcmljIG5vbi1saW5lYXIgb2JqZWN0aXZlczsgc3BlY2lhbCBjYXNlcyBvZiBzdWNoIG9iamVjdGl2ZXMgaGF2ZSBwcmV2aW91c2x5IGJlZW4gY29uc2lkZXJlZCwgcGFydGljdWxhcmx5IGZvciBlbmVyZ3kgbWluaW1pemF0aW9uLgogIEFzIGEgc3BlY2lmaWMgcHJvYmxlbSBpbiB0aGlzIGdlbnJlLCB3ZSBjb25zaWRlciB0aGUgdW5yZWxhdGVkIG1hY2hpbmUgc2NoZWR1bGluZyBwcm9ibGVtIHdpdGggc3RhcnR1cCBjb3N0cyBhbmQgYXJiaXRyYXJ5ICRcZWxsX3AkIG5vcm1zIG9uIG1hY2hpbmUgbG9hZHMgKGluY2x1ZGluZyB0aGUgc3VycHJpc2luZ2x5IG5vbi10cml2aWFsICRcZWxsXzEkIG5vcm0gcmVwcmVzZW50aW5nIHRvdGFsIG1hY2hpbmUgbG9hZCkuIFRoaXMgcHJvYmxlbSB3YXMgc3R1ZGllZCBlYXJsaWVyIGZvciB0aGUgbWFrZXNwYW4gbm9ybSBpbiBib3RoIHRoZSBvZmZsaW5lIChLaHVsbGVyfntcZW0gZXQgYWwufSwgU09EQSAyMDEwOyBMaSBhbmQgS2h1bGxlciwgU09EQSAyMDExKSBhbmQgb25saW5lIHNldHRpbmdzIChBemFyIHtcZW0gZXQgYWwufSwgU09EQSAyMDEzKS4gV2UgYWRhcHQgdGhlIHR3by1waGFzZSBhcHByb2FjaCBvZiBvYnRhaW5pbmcgYSBmcmFjdGlvbmFsIHNvbHV0aW9uIGFuZCB0aGVuIHJvdW5kaW5nIGl0IG9ubGluZSAodXNlZCBzdWNjZXNzZnVsbHkgdG8gbWFueSBsaW5lYXIgb2JqZWN0aXZlcykgdG8gdGhlIG5vbi1saW5lYXIgb2JqZWN0aXZlLiBUaGUgZnJhY3Rpb25hbCBhbGdvcml0aG0gdXNlcyBpZGVhcyBmcm9tIG91ciBnZW5lcmFsIGZyYW1ld29yayB0aGF0IHdlIGRlc2NyaWJlZCBhYm92ZSAoYnV0IGRvZXMgbm90IGZpdCB0aGUgZnJhbWV3b3JrIGV4YWN0bHkgYmVjYXVzZSBvZiBub24tcG9zaXRpdmUgZW50cmllcyBpbiB0aGUgY29uc3RyYWludCBtYXRyaXgpLiBUaGUgcm91bmRpbmcgYWxnb3JpdGhtIHVzZXMgaWRlYXMgZnJvbSBvZmZsaW5lIHJvdW5kaW5nIG9mIExQcyB3aXRoIG5vbi1saW5lYXIgb2JqZWN0aXZlcyAoQXphciBhbmQgRXBzdGVpbiwgU1RPQyAyMDA1OyBLdW1hciB7XGVtIGV0IGFsLn0sIEZPQ1MgMjAwNSkuIE91ciBjb21wZXRpdGl2ZSByYXRpbyBpcyB0aWdodCB1cCB0byBhIGxvZ2FyaXRobWljIGZhY3Rvci4gRmluYWxseSwgZm9yIHRoZSBpbXBvcnRhbnQgc3BlY2lhbCBjYXNlIG9mIHRvdGFsIGxvYWQgKCRcZWxsXzEkIG5vcm0pLCB3ZSBnaXZlIGEgZGlmZmVyZW50IHJvdW5kaW5nIGFsZ29yaXRobSB0aGF0IG9idGFpbnMgYSBiZXR0ZXIgY29tcGV0aXRpdmUgcmF0aW8gdGhhbiB0aGUgZ2VuZXJpYyByb3VuZGluZyBhbGdvcml0aG0gZm9yICRcZWxsX3AkIG5vcm1zLiBXZSBzaG93IHRoYXQgdGhpcyBjb21wZXRpdGl2ZSByYXRpbyBpcyBhc3ltcHRvdGljYWxseSB0aWdodC48L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/1412.3507","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-08T18:47:38.000Z","registered":"2022-03-08T18:47:44.000Z","published":"2014","updated":"2022-03-08T18:47:44.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1412.3507","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}